「力扣每日一题」两个字序列的最大点积动态规划还能这么用刷题群里看到有人讨论每日一题标题是“两个字序列的最大点积”。乍一看这题和常见的“子序列”“点积”都不太一样很多初学者第一反应是这不就是求两个数组的内积吗排序一下就能算如果你也这么想那我劝你停一停这道题如果真当成纯数学的内积来做可能要压制很久。先说它是什么这道题本质上是一个“带约束的子序列匹配问题”。给定两个序列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]之间任意抽取等长子序列能构造的最大点积。注意在此之前先要想清楚空子序列的问题。题目要求“非空子序列”但我们计算状态时会遇到i0或j0的边界——此时没有任何元素可选点积只能定义为“负无穷”用来表示“不存在这样的子序列”避免它参与后续比较时干扰有效结果。那状态转移方程怎么推核心思想是从后往前看最后一个匹配位置。假设我们已经处理到了(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长度为 mnums2长度为 n为了处理i-1和j-1不越界我会把 DP 表开成(m1) x (n1)的大小其中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(vectorint nums1, vectorint nums2) { int m nums1.size(), n nums2.size(); const int NEG_INF -1e9; // 只要比最小可能乘积负值小即可 vectorvectorint dp(m1, vectorint(n1, 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长度为n1初始全是NEG_INF。当外层i走第一行时cur更新为第一行结果。当走到第二行i2时我们需要同时知道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(vectorint nums1, vectorint nums2) { int m nums1.size(), n nums2.size(); const long long NEG_INF -1e18; vectorlong long dp(n1, 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 列的值作为下一轮j1状态的“左上角”。这个技巧在多种二维滚动数组 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]。若先匹配 111然后被迫匹配 (-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]。如果贪心先配 5525 再配 (-1)(-1)1总分 26最优其实是 25但 26 更大说明贪心在这个例子碰巧对了。反例比较难找其实这道题贪心失效的根源在于“要不要跳过开头的一部分”。举个例子nums1 [10, -1]nums2 [-1, 10]。贪心先配 10 * (-1) -10这会拉低总分最优可能是只配 (-1) 和 (-1) 1或者只配 1010100但 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 的表画出来推完没几行你就会发现状态转移方程到底在做什么比看任何题解都有用。
