「力扣每日一题」两个字序列的最大点积，动态规划还能这么用？
刷题群里看到有人讨论每日一题，标题是“两个字序列的最大点积”。乍一看，这题和常见的“子序列”“点积”都不太一样，很多初学者第一反应是：这不就是求两个数组的内积吗？排序一下就能算？如果你也这么想，那我劝你停一停，这道题如果真当成纯数学的内积来做，可能要压制很久。
先说它是什么：这道题本质上是一个“带约束的子序列匹配问题”。给定两个序列nums1和nums2，你需要从这两个序列中各选一个非空子序列，要求两个子序列长度相同，然后按位置一一对应，计算对应元素的乘积之和——这就是点积。目标就是让这个点积最大。
它能解决什么问题呢？从底层逻辑看，这是一种序列匹配、特征对齐、信号向量的相似度度量问题。比如两个时间序列的相似度比较、两段基因序列的碱基匹配、推荐系统里的用户兴趣曲线对齐，抽象出来都可能在处理“局部对齐以增加整体得分”这件事。适合谁来参考？如果你是刚接触动态规划的刷题者，这道题是很好的二维 DP 入门题；如果你是准备面试的选手，这题又非常容易考到——因为面试官特别喜欢把经典 LCS（最长公共子序列）变个形来考你。
我不打算只贴个题解草草了事，那没有意义。我以自己的刷题和理解过程为主线，把这题的思路掰开揉碎，连“为什么要这样定义状态”“为什么不能用贪心”“边界为什么这么设”——全部讲清楚。
1. 先搞清楚什么是“点积”，别一上来就排序
很多人第一眼看到“点积”两个字，马上联想到数学里的向量内积：sum(a_i * b_i)——两个向量对位相乘再求和。然后脑子里就开始盘算：那我把两个数组都从大到小排序，对应位相乘不就能最大了？甚至还有人直接想用贪心或者双指针。但注意，题目里有个前置条件：必须选出“子序列”，而不是“子数组”，也不是任意重排后的序列。
我先提醒一句：在算法题里，凡是提到子序列，默认是不能改变原始顺序的。你可以跳过某些元素，但你选出来的元素必须保留它们在原数组中的相对顺序。举个例子，nums1 = [1, 2, 3]，它可以选出子序列[1, 3]，但绝对不可能选出[3, 1]，因为顺序变了。所以“排序后相乘”这个思路一开始就跑偏了。
再说点积这个概念。既然两个子序列长度相同、位置一一对应，那么点积就是sum(nums1[i_k] * nums2[j_k])，其中i_k和j_k是两个子序列的原始下标序列。注意这里的下标序列是递增的。由于每个元素可以与对方序列中不同位置的元素匹配，所以其实这是一个“错位匹配”问题。哪怕是两个很普通的正数数组，不同的匹配方式，点积结果可能差异巨大。
举个简单例子。nums1 = [2, 1]，nums2 = [1, 3]。如果强制从第一个位置开始一一对应（索引对齐），点积是2*1 + 1*3 = 5。但如果我们跳过nums1的第二个元素1，只取第一个元素2，并从nums2中取第二个元素3，得到[2]和[3]，点积是6，比 5 大。你看，跳过某些元素往往能获得更好的匹配效果——这就是为什么这道题有意思，同时也说明它不能用简单的“从头扫到尾，见乘积为正就加，为负就减”的贪心思路来做，因为局部最优不等于全局最优。
再深看一层，这道题的本质是“两个序列之间如何寻找最优的对应关系”。如果两个元素乘积为正数，说明这两个元素同号，相乘能带来正向增益；如果乘积为负，说明异号，你就要掂量一下：是直接跳过划算，还是硬着头皮匹配但后续别的位置补回来？再如果乘积为零，则对结果无增益，选了也不影响得分，但占用了子序列长度和位置关系。这就是动态规划能够发挥作用的地方——每一步的最优决策可以通过子问题来递推，而不是靠单一维度的贪心判断。
2. 动手画 DP 表之前，先把状态定义想清楚
既然确定用动态规划，第一件事就是定义状态。动态规划的核心就是“用数组/表格记录中间结果，推到最后得到答案”。对于二维 DP 的题，状态定义通常是这样一句废话但极其关键的话：令dp[i][j]表示“nums1的前 i 个元素”和“nums2的前 j 个元素”作为可选项中，能得到的最大点积。
这里要仔细理解“前 i 个元素”。它不是说你必须取第 i 个、第 j 个，而是说在nums1[0..i-1]和nums2[0..j-1]之间任意抽取等长子序列，能构造的最大点积。注意，在此之前，先要想清楚空子序列的问题。题目要求“非空子序列”，但我们计算状态时会遇到i=0或j=0的边界——此时没有任何元素可选，点积只能定义为“负无穷”，用来表示“不存在这样的子序列”，避免它参与后续比较时干扰有效结果。
那状态转移方程怎么推？核心思想是：从后往前看最后一个匹配位置。假设我们已经处理到了(i, j)这个状态，第一步，要不要匹配nums1[i-1]和nums2[j-1]？这里分成两种情况来理解：
如果匹配它们两个：点积值就是
nums1[i-1] * nums2[j-1]，再加上之前的某个状态的最优值。因为一旦配对，i-1 和 j-1 两个位置都用掉了，那么就回到dp[i-1][j-1]的基础状态。但注意，dp[i-1][j-1]可能是负无穷（比如全是负数的情况），这时候直接加会导致匹配后的结果可能还是负的。所以正确的做法是：这个配对本身可以作为整个子序列的第一个（也是唯一一个）元素，直接取nums1[i-1] * nums2[j-1]；也可以接在前面的某个子序列之后，即用dp[i-1][j-1] + nums1[i-1] * nums2[j-1]。两者取大。如果不匹配它们两个：那么可能是
nums1[i-1]和别的元素匹配了（在更早的某列），也可能是nums2[j-1]和别的元素匹配了（在更早的某行），甚至两者都没被选入子序列。这种“弃用某些尾部元素”的情况，等价于从dp[i][j-1]或dp[i-1][j]继承过来，因为它们分别表示在处理到当前列/行之前，已经可以获得的最优结果。
到这里，有人会问：dp[i][j-1]和dp[i-1][j]那两个状态本身会不会产生冲突？比如dp[i][j-1]可能已经使用了nums1的第 i 个元素去匹配了前 j-1 个元素中的某个，而dp[i-1][j]又可能使用了nums2的第 j 个元素去匹配了前 i-1 个元素中的某个。这三个来源只是互相比较取最大值，而不是真正的计算路径叠加，所以不会冲突。它只关心“当前这个更大的候选集合下，能拿到的最优值是多少”。
状态方程总结起来就是这样：
dp[i][j] = max( dp[i-1][j], // 不使用 nums1[i-1] dp[i][j-1], // 不使用 nums2[j-1] dp[i-1][j-1] + nums1[i-1] * nums2[j-1], // 配对这两个元素 nums1[i-1] * nums2[j-1] // 仅配这两个作为首个元素 )注意方程里的那个“仅配这两个作为首个元素”分支很微妙。如果不加上它，在dp[i-1][j-1]是负无穷或负数特别大的时候，即使nums1[i-1] * nums2[j-1]是正数，我们也会因为-inf + 正数还是-inf而丢掉这个有效选项。所以这里一定要单独拿出来比较。这也是很多新手写这道题时最容易漏掉的一行代码。
还有一点需要特别强调：为什么取dp[i][j-1]和dp[i-1][j]而不是像传统 LCS 那样只取其中一个？传统 LCS 的状态递推中，因为字符相等时可以直接继承左上的状态，不相等才从上方/左方取最大。但本题的“点积”不是一种“相等/不等”的关系，任何时候我们都允许“跳过某个元素”，所以理论上每一格都同时受左、上、左上三个方向影响。这就是把这三个都写进转移方程的原因。
3. 边界条件与初始化，坑全藏在这里
说完状态转移，接下来就是另一大重灾区：边界和初始化。这道题非常容易在初始化和返回结果上翻车。
先明确 DP 表的维度。nums1长度为 m，nums2长度为 n，为了处理i-1和j-1不越界，我会把 DP 表开成(m+1) x (n+1)的大小，其中dp[0][j]和dp[i][0]全部初始化为负无穷。原因很简单：前 0 个元素意味着没有任何元素可选，此时不可能构造出合法的非空子序列，所以结果应该是“不可能”。用-inf表示这个语义，比用0合理得多。
但是，如果全表都初始化成-inf，还有一个坑：状态转移时，dp[i-1][j-1] + product如果前面是-inf，那结果还是-inf，只有“单配”分支能救回来，所以上面的转移方程里那个单独的分支不能省。
还有更微妙的一层：如果所有的乘积都是负数，怎么办？比如nums1 = [-1, -2]，nums2 = [-3, -4]，显然选[-1]和[-3]的点积是 3，是最大正数，因为负负得正。此时如果初始化全是0，就会出现“选零个元素加总是 0，比任何负数都大”的假象，最后你返回0而不是返回实际的负乘积。所以负无穷初始化的另一个作用就是保证“非空子序列”这个约束被强制满足。
那最终答案存在哪？就在dp[m][n]。很多人会问：为什么不直接在dp表更新过程中记录全局最大值？因为状态定义本身已经涵盖了“前 i 个元素和前 j 个元素的所有可能的非空子序列组合”，所以最大点积一定是所有表中的最大值，也就是右下角的dp[m][n]——除非我们把 DP 表定义成“必须使用最后一个元素”，那才需要额外的全局变量。我这里定义的是“可使用可不使用”，因此右下角天然就是答案。
再补充一个极容易被忽略的边界：两个数组长度为 1 的情况。比如nums1 = [5]，nums2 = [-2]。唯一的点积是5*(-2) = -10，你应该返回-10，而不是0。因为必须选一个元素配对，不能因为有负数就选择“空”。所以初始化负无穷这个细节在极端情况下直接决定了答案对错。
下面我放一段常见实现代码（C++ 版），并逐行解释每个关键部分：
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); const int NEG_INF = -1e9; // 只要比最小可能乘积（负值）小即可 vector<vector<int>> dp(m+1, vector<int>(n+1, NEG_INF)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { int prod = nums1[i-1] * nums2[j-1]; // 仅配对当前这两个元素作为新子序列的第一个元素 dp[i][j] = prod; // 接在某个更小的子序列之后 if (dp[i-1][j-1] != NEG_INF) { dp[i][j] = max(dp[i][j], dp[i-1][j-1] + prod); } // 不使用 nums1[i-1] dp[i][j] = max(dp[i][j], dp[i-1][j]); // 不使用 nums2[j-1] dp[i][j] = max(dp[i][j], dp[i][j-1]); } } return dp[m][n]; }这段代码里我特地写了一个NEG_INF = -1e9，从数值上保证它足够小，不会影响比较。但如果你把NEG_INF设成INT_MIN，就要小心了——如果你在代码里对NEG_INF做加法运算，比如dp[i-1][j-1] + prod，一旦dp[i-1][j-1]是INT_MIN，整型加法会直接溢出变成未定义行为，轻则答案错误，重则运行时崩溃。所以我的习惯是：用一个“足够负的有限值”，而不是INT_MIN。具体取多少，要看数据范围。如果nums元素大小不超过10^4，长度不超过 500，那么最大乘积绝对值不超过500 * 10^4 * 10^4 = 5e10，实际要更大一些。所以通常取-1e18（对应long long）这类值才保险。但如果数据范围小，-1e9也行，总之别用INT_MIN。
4. 从朴素二维 DP 到空间优化，以及滚动数组的写法
二维 DP 表清晰直观，但很多算法学习者会纠结一个问题：能不能把空间压缩到一维？答案是能。因为dp[i][j]的状态转移只依赖dp[i-1][j]（上方）、dp[i][j-1]（左方）和dp[i-1][j-1]（左上）。也就是说，每一行的计算只依赖“上一行”和“当前行左边的值”。那我们就可以只维护一个一维数组dp[j]，配合一个额外的变量来保存“左上角”的值。
具体操作是这样：外层循环遍历i，内层循环遍历j。在每一轮i开始之前，dp[j]存的是上一轮i-1的第 j 列值，也就是dp_prev[j]。在内层循环中，从左往右更新时，我们先保存当前dp[j]的旧值作为“当前 i 行、j-1 列”状态？不对，这里是容易混淆的地方，我画图讲一下。
假设数组叫cur，长度为n+1，初始全是NEG_INF。当外层i走第一行时，cur更新为第一行结果。当走到第二行i=2时，我们需要同时知道：
cur[j]（更新前）代表上一行的dp[i-1][j]cur[j-1]（更新后）代表当前行的dp[i][j-1]- 上一行的
dp[i-1][j-1]
难点在第三个。如果内层从左往右扫，当我们更新完cur[j-1]后，上一行的dp[i-1][j-1]已经被覆盖了。解决办法是在更新cur[j-1]之前，用一个变量prev_left先把它的旧值存下来，然后每次计算cur[j]时就使用这个prev_left。代码如下：
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); const long long NEG_INF = -1e18; vector<long long> dp(n+1, NEG_INF); for (int i = 1; i <= m; i++) { long long prev_left = NEG_INF; // 用于存上一行的 dp[j-1] for (int j = 1; j <= n; j++) { long long old = dp[j]; // 上一行的 dp[i-1][j] long long prod = 1LL * nums1[i-1] * nums2[j-1]; long long best = prod; if (prev_left != NEG_INF) { best = max(best, prev_left + prod); } if (old != NEG_INF) { best = max(best, old); } if (dp[j-1] != NEG_INF) { best = max(best, dp[j-1]); } dp[j] = best; prev_left = old; // 这一轮的 old 就是下一轮需要的"左上角" } } return dp[n]; }这里有个细节：prev_left到底存什么？在每次内层循环里，更新dp[j]之前，old = dp[j]是上一行的第 j 列值；而prev_left存的是上一行的第 j-1 列值——正好就是dp[i-1][j-1]。更新完dp[j]后，我们把prev_left更新为old，也就是把上一行第 j 列的值作为下一轮（j+1）状态的“左上角”。这个技巧在多种二维滚动数组 DP 里通用，初学者可以记下来。
如果你觉得滚动数组容易写错，我建议第一版直接写二维 DP，毕竟大多数在线评测的内存限制对500 x 500这种规模还是很宽容的。空间优化是在你完全理解二维 DP 之后，再动手做的进阶操作，不要为了炫技而牺牲正确性。
5. 为什么不能贪心、不能排序、不能双指针——常见误区大盘点
我把这道题常见错解整理了一下，每一条都是我实际刷题时见过别人踩过的，或者是自己第一反应踩中的坑：
误区一：排序后按位相乘。大错特错。子序列的本质是保序，一旦排序就改变了原序列的匹配关系。比如
nums1 = [1, 100]，nums2 = [100, 1]。排序后变成[1,100]和[1,100]，点积是 101；但原来的最优解是选nums1[1]和nums2[0]配对，也就是 100 * 100 = 10000。排序直接破坏了最优匹配的可能。误区二：双指针贪心，哪个乘积大就匹配哪个。初看似乎合理，但问题是“跳过哪个元素才能让全局最优”往往需要动态规划才能判断。比如
nums1 = [1, -5]，nums2 = [1, -1]。若先匹配 11=1，然后被迫匹配 (-5)(-1)=5，总分 6。但最优解是匹配 (-5) 和 (-1)，得到 5，把前面的 1 跳过，同样总分 5？不对，其实最优是配 1*(-1)=-1 或中间跳过？仔细分析：直接只匹配 (-5)(-1)=5 优于 1 + 5 = 6？等一下，6 > 5，所以 6 是最优。这个例子不能说明问题，换一个：nums1 = [-1, 5]，nums2 = [5, -1]。如果贪心先配 55=25 再配 (-1)(-1)=1，总分 26，最优其实是 25，但 26 更大，说明贪心在这个例子碰巧对了。反例比较难找？其实这道题贪心失效的根源在于“要不要跳过开头的一部分”。举个例子，nums1 = [10, -1]，nums2 = [-1, 10]。贪心先配 10 * (-1) = -10？这会拉低总分；最优可能是只配 (-1) 和 (-1) = 1，或者只配 1010=100？但 10 在 nums1 第一位，nums2 的 10 在第二位，顺序上可以配，中间隔着一个位置，没问题，所以最优点是 100。如果用贪心从头开始看，可能会因为第一对 10*(-1)=-10 是负数就直接跳过，但它判断不了后面还有更好的匹配。这类问题本质上还是要枚举所有子序列组合的。误区三：以为必须“连续子数组”。如果题目是子数组，那解法就是最大子数组和，直接 Kadane 算法即可。但这里是子序列，中间可以跳任意多个元素，这是难度上一个很大的跳跃。
误区四：初始化 DP 表为 0。会导致全负数用例出错，前面已经详细讲过。
误区五：认为存在“序列为空”的分支，返回 0。这题明确要求非空子序列，所以空集不是合法答案。负无穷初始化强行绕开了这个坑。
误区六：状态转移时只写了
dp[i-1][j-1] + prod而没有单独写prod。这在所有乘积都是正数且 dp 前缀都正常的情况下可能侥幸通过，但只要遇到前序 dp 是负数，立刻出错。
这些误区每一个我都实际看到过，有的甚至出现在某些讨论区的“高赞题解”里。我自己第一次写的时候也掉进过“排序解法”的坑里，后来对着一个简单反例跑了一遍才恍然大悟。所以看到这题的你别急，踩坑本身就是学习的一部分。
6. 从这题能学到什么，又如何举一反三
这道题虽然是力扣每日一题里的中等题，但它把两个非常重要的动态规划思想揉在了一起：第一，状态需要记录两个序列各自的前缀范围，本质是二维 DP；第二，允许跳过元素的灵活性，让问题比固定长度匹配复杂得多。
如果你已经能不看题解自己写出二维 DP 的状态转移方程，那么接下来可以思考这些变体，用来检验自己是不是真懂了：
变体一：如果改为“最大子序列和点积”，要求两个子序列至少长度为一，但元素乘积可以是负数，你怎么改状态？答案其实不用改，因为我们本来就不要求全正。
变体二：如果序列元素都为正数，这题的答案是不是就退化成“取每个序列中的最大正数相乘”？不是，因为虽然正数相乘都是增益，但如果你取了两个正数分别相乘，可能更大的数在各自序列里，另外的匹配可以叠加得分。比如nums1 = [10, 1]、nums2 = [10, 1]，最优是 1010 + 11 = 101，而只取最大相乘得 100。当然，也有“为了更大的匹配而牺牲小匹配”的情况，这也说明了 DP 的必要性。
变体三：如果改成“最长公共子序列”那样，要求匹配元素相等，那状态转移就变成 LCS 的经典形式。你如果能从本题的转移方程反推出 LCS 的方程，说明你对“子序列 DP”的理解已经到位了。
再想想实际运用。序列之间的“局部匹配最优化”在很多工业场景里都有影子。比如两个传感器采集到的时间序列，长度不同、噪声很多，你想找出“最相似”的那两段——这两个问题本质上是“对齐”问题，而对齐又和“最大点积”有千丝万缕的关系。推荐系统里，用户行为序列和商品特征序列做匹配，也经常用这一类带跳过的相似度计算。你学会了这道题，以后再看到序列匹配问题，至少能一眼识别出“这是不是 DP 能解决的问题”。
还有一个常见延伸是“最大子矩阵和”，如果你把 DP 表本身当作矩阵，状态从左上角出发，依赖左、上、左上三个方向——这其实就是二维前缀和的变体，和“最大子矩阵和”的计算逻辑有异曲同工之处。
我个人练题的经验是：每日一题这种形式之所以值得坚持，恰恰是因为它把零碎的知识点串起来了。今天你学的是“最大点积”，明天可能就是“编辑距离”，后天是“正则表达式匹配”。它们的 DP 表都是二维的，转移方向大同小异，关键区别就在“状态定义怎么切分问题的边界”。当你刷到第十几道二维 DP 题时，你会发现自己不需要再画表就能直接写出代码——那种手感，是靠一道一道题慢慢堆起来的。
最后再分享一个我每次做 DP 题都会用的小技巧：先纸上画一个小用例的 DP 表，手动推几行，再动笔写代码。不要觉得浪费时间，这是我刷题多年唯一确定的、能显著降低错误率的方法。像这道题，你随便拿nums1 = [2,1,-1]、nums2 = [3,-1,1]试试，把 4x4 的表画出来，推完没几行你就会发现状态转移方程到底在做什么，比看任何题解都有用。
