一、寻找子问题
为方便描述，下文把 $\textit{nums}_1$ 和 $\textit{nums}_2$ 简称为 $a$ 和 $b$。
在示例 1 中，我们要解决的问题（原问题）是：
- 从 $a=[2,1,-2,5]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列 $c$ 和 $d$，计算 $c$ 和 $d$ 的点积的最大值。
⚠注意：选出的子序列必须是非空的。
考虑从右往左选数字，用「选或不选」分类讨论：
- 选 $a[3]$ 和 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的子序列，计算两个子序列点积的最大值。由于我们选了元素，所以子序列可以为空。但这样思考的话，子问题就和原问题不相似了。为了保证子问题和原问题相似，我们可以再细分为两种情况：
- 选 $a[3]$ 和 $b[2]$，且前面不再选数字。这意味着点积就是 $a[3]\cdot b[2]$。
- 选 $a[3]$ 和 $b[2]$，且前面还要选数字。需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
- 不选 $a[3]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
- 不选 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2,5]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
由于选或不选都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。
注 1：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。
注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。子序列相邻无关一般是「选或不选」，子序列相邻相关（例如 LIS 问题）一般是「枚举选哪个」。本题用到的是「选或不选」。
二、状态定义与状态转移方程
根据上面的讨论，定义状态为 $\textit{dfs}(i,j)$，表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
接下来，思考如何从一个状态转移到另一个状态。
用「选或不选」分类讨论：
- 选 $a[i]$ 和 $b[j]$，且前面不再选数字。这意味着点积就是 $a[i]\cdot b[j]$。
- 选 $a[i]$ 和 $b[j]$，且前面还要选数字。需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j-1)$。再加上 $a[i]\cdot b[j]$，就得到了 $\textit{dfs}(i,j)$。
- 前两种情况可以合并为：$\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j]$。
- 不选 $a[i]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j)$。
- 不选 $b[j]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i,j-1)$。
这四种情况取最大值，就得到了 $\textit{dfs}(i,j)$，即
$$
\textit{dfs}(i,j) = \max{\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j], \textit{dfs}(i-1,j),\textit{dfs}(i,j-1)}
$$
递归边界：$\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。此时其中一个数组没有元素，无法选出非空子序列，不合法。用 $-\infty$ 表示不合法的状态，从而保证 $\max$ 不会取到不合法的状态。
递归入口：$\textit{dfs}(n-1,m-1)$，这是原问题，也是答案。其中 $n$ 是 $a$ 的长度，$m$ 是 $b$ 的长度。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
- 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
- 如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。
⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$，但本题子序列点积可能是负数，可以初始化为 $\infty$。
Python 用户可以无视上面这段，直接用 @cache 装饰器。
具体请看视频讲解 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。
###py
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
# 返回从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, j: int) -> int:
if i < 0 or j < 0:
# 其中一个数组没有元素，无法选出非空子序列
return -inf # 下面计算 max 不会取到无解情况
# 选 nums1[i] 和 nums2[j]
# 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
res1 = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j]
# 不选 nums1[i]
res2 = dfs(i - 1, j)
# 不选 nums2[j]
res3 = dfs(i, j - 1)
return max(res1, res2, res3)
return dfs(len(nums1) - 1, len(nums2) - 1)
###java
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[][] memo = new int[n][m];
for (int[] row : memo) {
Arrays.fill(row, Integer.MAX_VALUE);
}
return dfs(n - 1, m - 1, nums1, nums2, memo);
}
// 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
private int dfs(int i, int j, int[] nums1, int[] nums2, int[][] memo) {
if (i < 0 || j < 0) {
// 其中一个数组没有元素，无法选出非空子序列
return Integer.MIN_VALUE; // 下面计算 max 不会取到无解情况
}
if (memo[i][j] != Integer.MAX_VALUE) { // 之前计算过
return memo[i][j];
}
// 选 nums1[i] 和 nums2[j]
// 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
int res1 = Math.max(dfs(i - 1, j - 1, nums1, nums2, memo), 0) + nums1[i] * nums2[j];
// 不选 nums1[i]
int res2 = dfs(i - 1, j, nums1, nums2, memo);
// 不选 nums2[j]
int res3 = dfs(i, j - 1, nums1, nums2, memo);
memo[i][j] = Math.max(res1, Math.max(res2, res3)); // 记忆化
return memo[i][j];
}
}
###cpp
class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector memo(n, vector<int>(m, INT_MAX));
// 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
auto dfs = [&](this auto&& dfs, int i, int j) -> int {
if (i < 0 || j < 0) {
// 其中一个数组没有元素，无法选出非空子序列
return INT_MIN; // 下面计算 max 不会取到无解情况
}
int& res = memo[i][j]; // 注意这里是引用
if (res != INT_MAX) { // 之前计算过
return res;
}
// 选 nums1[i] 和 nums2[j]
// 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
res = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j];
// 不选 nums1[i]
res = max(res, dfs(i - 1, j));
// 不选 nums2[j]
res = max(res, dfs(i, j - 1));
return res;
};
return dfs(n - 1, m - 1);
}
};
###go
func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m)
for j := range memo[i] {
memo[i][j] = math.MaxInt
}
}
// 从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
var dfs func(int, int) int
dfs = func(i, j int) int {
if i < 0 || j < 0 {
// 其中一个数组没有元素，无法选出非空子序列
return math.MinInt // 下面计算 max 不会取到无解情况
}
p := &memo[i][j]
if *p != math.MaxInt { // 之前计算过
return *p
}
// 选 nums1[i] 和 nums2[j]
// 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
res1 := max(dfs(i-1, j-1), 0) + nums1[i]*nums2[j]
// 不选 nums1[i]
res2 := dfs(i-1, j)
// 不选 nums2[j]
res3 := dfs(i, j-1)
*p = max(res1, res2, res3) // 记忆化
return *p
}
return dfs(n-1, m-1)
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(nm)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(nm)$。
- 空间复杂度：$\mathcal{O}(nm)$。保存多少状态，就需要多少空间。
四、1:1 翻译成递推
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，$f[i+1][j+1]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。这里 $+1$ 是为了把 $\textit{dfs}(-1,j)$ 和 $\textit{dfs}(i,-1)$ 也翻译过来，这样我们可以把 $f[0][j]$ 和 $f[i][0]$ 作为初始值。
相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：
$$
f[i+1][j+1] = \max{\max(f[i][j], 0) + a[i]\cdot b[j], f[i][j+1],f[i+1][j]}
$$
初始值：$f$ 第一行和第一列初始化成 $-\infty$，翻译自递归边界 $\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。
答案为 $f[n][m]$，翻译自递归入口 $\textit{dfs}(n-1,m-1)$。
###py
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
n, m = len(nums1), len(nums2)
f = [[-inf] * (m + 1) for _ in range(n + 1)]
for i, x in enumerate(nums1):
for j, y in enumerate(nums2):
f[i + 1][j + 1] = max(max(f[i][j], 0) + x * y, f[i][j + 1], f[i + 1][j])
return f[n][m]
###java
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[][] f = new int[n + 1][m + 1];
for (int[] row : f) {
Arrays.fill(row, Integer.MIN_VALUE);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
f[i + 1][j + 1] = Math.max(
Math.max(f[i][j], 0) + nums1[i] * nums2[j],
Math.max(f[i][j + 1], f[i + 1][j])
);
}
}
return f[n][m];
}
}
###cpp
class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector f(n + 1, vector<int>(m + 1, INT_MIN));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int res1 = max(f[i][j], 0) + nums1[i] * nums2[j];
// 注：max({...}) 比 max(..., max(...)) 慢
f[i + 1][j + 1] = max(res1, max(f[i][j + 1], f[i + 1][j]));
}
}
return f[n][m];
}
};
###go
func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
for j := range f[i] {
f[i][j] = math.MinInt
}
}
for i, x := range nums1 {
for j, y := range nums2 {
f[i+1][j+1] = max(max(f[i][j], 0)+x*y, f[i][j+1], f[i+1][j])
}
}
return f[n][m]
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
- 空间复杂度：$\mathcal{O}(nm)$。
五、空间优化
类似 1143. 最长公共子序列 的空间优化方法，只用一个长为 $m+1$ 的一维数组，原理讲解请看 最长公共子序列 编辑距离【基础算法精讲 19】。
###py
# 更快的写法见【Python3 手写 max】
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums2)
f = [-inf] * (m + 1)
for x in nums1:
pre = f[0]
for j, y in enumerate(nums2):
tmp = f[j + 1]
f[j + 1] = max(max(pre, 0) + x * y, f[j + 1], f[j])
pre = tmp
return f[m]
###py
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums2)
f = [-inf] * (m + 1)
for x in nums1:
pre = f[0]
for j, y in enumerate(nums2):
tmp = f[j + 1]
res = x * y
if pre > 0: res += pre
if f[j] > res: res = f[j]
if f[j + 1] > res: res = f[j + 1]
f[j + 1] = res
pre = tmp
return f[m]
###java
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int m = nums2.length;
int[] f = new int[m + 1];
Arrays.fill(f, Integer.MIN_VALUE);
for (int x : nums1) {
int pre = f[0];
for (int j = 0; j < m; j++) {
int tmp = f[j + 1];
f[j + 1] = Math.max(Math.max(pre, 0) + x * nums2[j], Math.max(f[j + 1], f[j]));
pre = tmp;
}
}
return f[m];
}
}
###cpp
class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int m = nums2.size();
vector<int> f(m + 1, INT_MIN);
for (int x : nums1) {
int pre = f[0];
for (int j = 0; j < m; j++) {
int tmp = f[j + 1];
f[j + 1] = max(max(pre, 0) + x * nums2[j], max(f[j + 1], f[j]));
pre = tmp;
}
}
return f[m];
}
};
###go
func maxDotProduct(nums1, nums2 []int) int {
m := len(nums2)
f := make([]int, m+1)
for i := range f {
f[i] = math.MinInt
}
for _, x := range nums1 {
pre := f[0]
for j, y := range nums2 {
tmp := f[j+1]
f[j+1] = max(max(pre, 0)+x*y, f[j+1], f[j])
pre = tmp
}
}
return f[m]
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
- 空间复杂度：$\mathcal{O}(m)$。
专题训练
见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
- 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
{:width=360px}
这里的 Σ 指示总和符号。
