刷动态规划刷到第四十三天说实话到这个阶段很多人已经有点晕了。前面的背包问题刚消化完今天又上来四道子序列相关的题——1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列。如果你正在跟代码随想录的算法营或者自己在刷题应该能感觉到这四道题放一起不是随便排的。它们的核心全是“子序列/子数组 动态规划”而且一旦你吃透了第一道后面三道都是它的变体或简化版。这篇文章就按我自己的刷题顺序把这四道题从题目理解、状态定义到递推公式、代码实现完整过一遍最后把最容易踩的坑也一起列出来。1. 先拆题这四道题背后的共同套路1.1 一道漫画题引出的子序列DP体系最长公共子序列LCS这类题很多人在校招笔试里都见过但第一次接触容易懵两个字符串放在一起要求找出最长的、保持相对顺序的公共部分怎么用代码表达“保持相对顺序”答案是这四道题共用同一种状态思维用二维DP去记录两个序列从头到某个位置已经匹配的结果。LCS看的是两个字符串不相交的线看的是两个数组判断子序列本质上是LCS的简化特例唯一看起来不一样的是最大子序和它是一维数组上求连续一段的最大和。第一道题研究透了后面的代码几乎不用换脑。我自己的体会是动态规划最难的一步不是写递推公式而是定义dp[i][j]到底代表什么。这四道题里除了最大子序和另外三道题都可以用同一个dp定义往下走长度为 i 的序列A与长度为 j 的序列B它们之间能构成某种“公共”关系的最大长度。有了这个统一视角题目看起来就不吓人了。1.2 DP数组多开一位的好处细心的同学应该发现了三道子序列题的代码里dp数组的尺寸都是 (len1 1) × (len2 1)而不是直接用 len1 × len2。我当时也困惑过为什么不直接用原长度。因为状态转移时会出现 i - 1 和 j - 1 的访问如果 dp 数组尺寸和原序列一样大i 0 时 i - 1 就越界了。多开一位让下标从 1 开始遍历dp[i][j] 对应的实际上是原序列第 i 个和第 j 个字符dp[0][j] 和 dp[i][0] 单独留出来表示“空串”的情况。这个设计不只是为了方便它天然处理了边界任何一个序列为空时公共子序列长度只能是 0。提示以后凡是遇到两个序列的DP题先默认把dp数组开成 (n1)*(m1)用空串做初始化基底再考虑状态转移能省掉一多半的边界焦虑。2. 1143 最长公共子序列二维DP的基本盘2.1 为什么不能用一维DP解决先明确一下最长公共子序列和最长公共子数组不一样。子数组要求连续子序列只要求相对顺序一致。连续问题用一维DPdp[i] 只管“以第 i 个元素结尾”但子序列不连续时某个字符可能跳过前面若干字符去匹配状态就必须要记录两个序列各自走到了哪里于是二维DP成了自然选择。举个例子text1 abcdetext2 ace。公共子序列是 ace长度 3。注意 a、c、e 在 text1 里中间分别隔了 b 和 d如果只用一个一维数组根本没地方记录这种“跳过”的信息。2.2 递推公式的分支逻辑定义 dp[i][j] 表示 text1 中前 i 个字符与 text2 中前 j 个字符的最长公共子序列长度。这里“前 i 个”指的是从下标 0 到 i-1 这一整段。当 text1[i-1] text2[j-1] 时说明当前两个字符可以配成一对那么长度就是两边各往前缩一格的结果加 1dp[i][j] dp[i-1][j-1] 1当 text1[i-1] ! text2[j-1] 时当前字符不能配对但两个字符串里可能还有别的组合。这时应该继承哪边的结果要么是 text1 前 i-1 个字符和 text2 前 j 个字符的最长结果要么是 text1 前 i 个字符和 text2 前 j-1 个字符的最长结果取较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])这个 max 是关键中的关键它本质上是说“当前字符不等的时候我选择丢掉 text1 的最后一个字符或者丢掉 text2 的最后一个字符看哪边保留的公共长度更长。”为了让这个逻辑更好记我每次都会默念一遍“不等就各退一步比大小”。2.3 初始化与遍历顺序初始化dp[0][j] 和 dp[i][0] 全部为 0因为任意一个字符串为空时最长公共子序列长度就是 0。遍历顺序i 从 1 到 len1j 从 1 到 len2两层循环嵌套先外层后内层即可。观察状态转移方程dp[i][j] 依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]这三个方向分别来自左上、上方和左方只要我们按行从上往下、每行从左往右遍历所有依赖的值都在之前算好了。text1 abcde, text2 ace 的dp表 a c e 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3表格右下角 3 就是最终答案。建议新手自己手动填一遍这张表对递推的理解远超看十遍代码。2.4 完整代码与逐行解读class Solution { public: int longestCommonSubsequence(string text1, string text2) { vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0)); for (int i 1; i text1.size(); i) { for (int j 1; j text2.size(); j) { if (text1[i - 1] text2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[text1.size()][text2.size()]; } };这里有几个细节值得注意。第一循环里用i text1.size()而不是i text1.size()因为 dp 数组下标和字符串下标差一位。第二比较时用的是text1[i - 1]而不是text1[i]这个偏移特别容易写错写错了编译器不报错但答案全错。第三max(dp[i - 1][j], dp[i][j - 1])这个分支里不需要考虑 dp[i-1][j-1]因为取 max 时 dp[i-1][j] 和 dp[i][j-1] 已经覆盖了它。注意如果题目现在变成长度可能达到 1000 甚至更大可以用滚动数组压缩空间。具体做法是把二维数组换成两行每次只保留当前行和上一行因为 dp[i][j] 最多依赖 dp[i-1][...] 和 dp[i][...] 这两行。面试时可以先说二维版再说优化版印象分会好不少。3. 1035 不相交的线披着连线外衣的LCS3.1 怎么一眼看穿这是LCS变体题目要求把 nums1 中某些数字与 nums2 中相同数字连成线任意两条线不能相交求最多能连多少条。我第一次看到这题时画了半天图想着是不是某种区间贪心。后来把题目换了个说法才恍然大悟如果按顺序从 nums1 选出几个数再按顺序从 nums2 选出几个数让它们两两相等那么连线天然就是不相交的。所谓不相交本质就是要求两个数组里的匹配顺序一致不能出现先匹配后面的数、再匹配前面的数的情况。这恰好和子序列的定义一模一样保持相对顺序。于是问题就变成了“nums1 和 nums2 的最长公共子序列长度”。字符换成数字而已连代码都不用重新想。3.2 代码对比只有变量名不同class Solution { public: int maxUncrossedLines(vectorint nums1, vectorint nums2) { vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0)); for (int i 1; i nums1.size(); i) { for (int j 1; j nums2.size(); j) { if (nums1[i - 1] nums2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[nums1.size()][nums2.size()]; } };和 1143 题的代码逐行对比唯一的区别就是比较的对象从字符变成了整数其余一模一样。这也印证了刷题时的一个经验题目里的元素类型只是外壳状态定义和转移逻辑才是内核。从这道题以后我遇到陌生题会先尝试把它翻译成已知的模型而不是一上来就硬想新解法。为了加深理解我给一个小例子。nums1 [1,4,2]nums2 [1,2,4]。能连的线最多是 2比如连 1-1 和 2-2如果选 1-1 和 4-4中间那条 2-2 插不进去而且会交叉。LCS 结果就是 2。手动模拟一遍你会发现 dp 表里所有路径都是“从左到右、从上到下”推进的这条推进路径映射到原数组上就是不相交连线。3.3 作图理解为什么公共子序列一定不相交你可以想象两个数组排成上下两行下标都从左往右增大。连线如果相交必然意味着上面选了后边的元素去匹配下面前边的元素而前面又选了另一个元素去匹配后面这就在顺序上出现了交叉。公共子序列的选取过程是从左往右同步扫描的每走一步两边下标都只增不减所以映射到连线图里每一条线都比上一条靠右自然不相交。实操心得做这类“换皮题”时建议把题目重新用自己的话复述一遍比如“最多能连多少条不相交的线”可以复述成“按从左到右的顺序最多能匹配多少对相同数字”。一旦复述成功解题思路基本就出来了。4. 53 最大子序和一维DP和贪心的两套打法4.1 状态定义以 i 结尾是突破口最大子序和求的是数组里连续子数组的最大和。之前几天的题目接触过“以 i 结尾”这种状态定义吗接触过最长递增子序列那题就是。这个定义的好处在于连续子数组如果要延续只能接在最后一个元素后面所以“以 nums[i] 结尾的最大子数组和”只有两种可能——要么自己单独成一个子数组要么接上前面的连续段。这里我先用 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。4.2 递推公式与结果收集接着上面的定义dp[i] 的两种来源分别是接上前面的连续段dp[i-1] nums[i]自己重新开始nums[i]取较大值dp[i] max(dp[i-1] nums[i], nums[i])注意这里安排的陷阱有些人会把 dp[i] 理解成“前 i 个元素里最大子序和”那 dp[i] max(dp[i-1], dp[i-1] nums[i]) 之类这个写法表达不清楚连续的要求容易漏掉从中间开始的情况。以 i 结尾的定义虽然多了一步“遍历 dp 找最大值”但语义无比准确。为什么结果不能直接返回 dp[n-1]因为最大子数组不一定以最后一个元素结尾。比如 [-2,1,-3,4,-1,2,1,-5,4]最大子数组是 [4,-1,2,1]和是 6它结束在索引 6而数组末尾是索引 8 的 4。所以每次算出 dp[i] 后要顺手更新一个 result。class Solution { public: int maxSubArray(vectorint nums) { vectorint dp(nums.size()); dp[0] nums[0]; int result dp[0]; for (int i 1; i nums.size(); i) { dp[i] max(dp[i - 1] nums[i], nums[i]); result max(result, dp[i]); } return result; } };初始化时 dp[0] nums[0]result 也先等于 nums[0]。如果数组只有一个元素直接返回它。很多人写 DP 时容易把 dp[0] 初始化为 0但子数组至少包含一个元素这一步错了整个答案都会歪。4.3 贪心解法与DP的精髓对比这题还有著名的贪心写法思路是在遍历数组时维护一个连续和 count一旦 count 小于 0就把它重置为 0因为负数对后续的和只会有拖累。每加一个数更新一次全局最大值。class Solution { public: int maxSubArray(vectorint nums) { int result INT_MIN; int count 0; for (int i 0; i nums.size(); i) { count nums[i]; if (count result) result count; if (count 0) count 0; } return result; } };两种写法的时间复杂度都是 O(n)。面试时先说贪心代码短如果被要求说明正确性再引出 DP 的状态定义来分析这样显得对问题理解深刻。我自己在刷题营里见过不少同学纠结“到底该学哪种”我的建议是都要掌握因为 DP 的“以 i 结尾”状态定义在很多进阶题里是基础而贪心的断点重置思路在区间类问题里也会复用。常见误解有人以为最大子序和必须从 dp 数组中取最大值所以提醒一下dp[i] 的语义是“以 i 结尾”不是“前 i 个的最优值”这两者差别很大。搞混了就会漏掉真正的最优子数组。5. 392 判断子序列双指针秒杀与DP思路对照5.1 双指针解法最简单的一版题目给定 s 和 t问 s 是否是 t 的子序列。最直观的解法是双指针两个指针分别扫描 s 和 t每在 t 中找到一个与 s 当前字符相等的字符s 的指针就前进一步。循环结束以后如果 s 的指针走到了末尾说明 s 中所有字符都在 t 中按顺序找到了匹配。class Solution { public: bool isSubsequence(string s, string t) { int i 0; for (int j 0; j t.size(); j) { if (i s.size() s[i] t[j]) i; } return i s.size(); } };这个解法的时间复杂度是 O(len(t))空间 O(1)。只要理解了“按顺序匹配”的含义写出这段代码只需要一分钟。很多人在循环里忘写i s.size()这个条件导致 s 已经全匹配上了还在继续比较虽然 s 后面没有字符了不会越界因为 s[i] 在 i size 时是未定义行为实际上有的编译器会返回 0 或直接崩但这是隐藏的 bug笔试时很可能查不出来。5.2 动态规划解法和LCS的血缘关系判断子序列本质上可以看作 LCS 的特例s 是 t 的子序列等价于 s 和 t 的最长公共子序列长度等于 s 的长度。如果 s 中的每个字符都能按顺序匹配上那么公共子序列长度就会达到 s 的完整长度。反过来如果中间有某个字符匹配不上公共子序列长度必然小于 s 的长度。所以直接复用 LCS 的模板最后判断一下结果class Solution { public: bool isSubsequence(string s, string t) { vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0)); for (int i 1; i s.size(); i) { for (int j 1; j t.size(); j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[s.size()][t.size()] s.size(); } };当 s 很长、且后续要求处理一系列查询时可以预计算 t 的后缀信息再用二分或跳跃匹配但这是进阶话题了。这里 DP 版的意义不完全在于性能而是帮助你建立“动态规划模型可以套用到不同题目”的直觉。我自己刷到后面越发觉得动态规划题的变体不是让你背代码而是训练识别“状态”和“决策”的能力。5.3 四道题横向对比代码模板总结把四道题的解法放一起看会发现一个很有意思的规律题目输入形式DP维度核心递推输出1143 最长公共子序列两个字符串二维相等走左上1不等取maxdp[n][m]1035 不相交的线两个数组二维同上dp[n][m]53 最大子序和一个数组一维延续或重启取maxmax(dp[i])392 判断子序列两个字符串二维/双指针LCS模板判等号dp[n][m] len(s)这个表我建议收藏。做题时一旦判断题目是“双序列保持顺序匹配”直接把它映射到 LCS 模板上一旦是“单序列连续子段最优”映射到最大子序和的状态定义上。动态规划不背题背的是这些题型指纹。6. 刷题实录这四道题最容易踩的几个坑6.1 偏移位错误i-1 写成 i这是我刷这组题时最常犯的错误也几乎是所有初学 LCS 的人都会踩的坑。dp[i][j] 对应原序列的前 i 个元素最后一个元素的下标是 i-1。比较时写text1[i] text2[j]不会报编译错误但 dp[0][0] 对应空串你根本访问不到 text1[0]于是第一个字符永远匹配不上整个答案错得离谱。建议写完后自己用短例子推一遍。比如 text1 a, text2 adp[1][1] 应该等于 1如果代码里写成了text1[1]直接越界。动手验证比背诵“注意偏移”有效得多。6.2 结果取错位置把 dp[n-1] 当成答案最大子序和这题里最终答案是所有 dp[i] 的最大值而不是 dp[n-1]。1143 题里答案是 dp[len1][len2]没有这个问题。但一到 53 题很多刚学 DP 的就惯性思维了觉得最后一个状态就是答案。最大子序和因为“以 i 结尾”的语义最优子段可以结束在任意位置所以必须遍历收集最大值。一个记忆技巧状态定义里带“结尾”两个字输出就要扫一遍 dp 取最优。带“前 i 个”字眼的状态输出通常就是 dp[n]。这组题目刚好两种类型都覆盖了正好对比着记。6.3 判断子序列时把子串当成子序列另一个容易出错的点是概念混淆。子串要求连续子序列不要求连续。s abct aebfcs 是 t 的子序列a、b、c 各自跳过了字母但不是连续子串。如果你用找子串的思维去套比如用 KMP 或者滑动窗口会直接得到错误答案。所以我也在提醒自己做题前先圈出题目关键词。看到“subsequence”默认用子序列那套看到“subarray”考虑连续子数组和“以 i 结尾”的 DP看到“substring”才用滑窗和 KMP 相关技巧。6.4 如何练习建议的刷题顺序如果只做一道先做 1143把二维 DP 的推导过程彻底弄懂。然后做 1035当作默写题验证自己能不能独立写出和 1143 几乎一样的代码。接着做 392先写双指针再用 LCS 模板写一版。最后做 53体会一维 DP 和贪心两种解法。这样一个流程下来四道题不是孤立记忆而是一套知识体系。我在刷题营的群里看大家讨论最高频的问题不是“这题怎么做”而是“为什么我跟答案写得一样却超时”或“为什么我的 dp 表长这样”。超时通常是因为三层循环比如多写了一层不必要的循环dp 表长得不对九成是偏移位和初始化的问题。遇到这类问题先打印 dp 表对着图找错比盯着代码干想效率高很多。最后说点个人经验。我刷到第四十三天最大的感受是动态规划题目看似千变万化但核心逃不出几套状态定义和决策分支。今天这四道题正好是很好的样例LCS 让你理解二维状态如何同步推进两个序列不相交的线告诉你换皮题怎么识别最大子序和让你记住“以 i 结尾”的状态如何配合全局最大值判断子序列则展示了同样的模型既能用双指针快速解决也能用 DP 一套逻辑包打天下。后面再遇到类似的题比如编辑距离、回文子序列你会发现今天的代码模板依然在那里。建议把这四道题反复刷刷到不看题解也能流畅写出那时候子序列动态规划这关才算真正过了。