2. 动态规划入门从最长公共子序列到最大子序和1. 内容整体设计与思路拆解刷到第43天动态规划已经进入“序列问题”的核心区域。今天这四道题放在一起其实有很清晰的递进关系1143最长公共子序列是基础母题1035不相交的线是它的换皮版本392判断子序列是退化版本而53最大子序和则完全是另一个维度的问题。把它们放在同一天就是为了让你一次性吃透“两个序列之间怎么比较”“一个序列内部怎么分段”这两类DP模型的思考方式。我在实际刷题时的一个体会是DP题目最怕的不是代码写不出来而是状态定义没想清楚就动手。今天这几道题正好能帮你建立一套判断套路看到“两个字符串/数组”“求公共部分”“求顺序关系”这些关键词优先往二维DP上想看到“一个数组”“连续子数组”“最大和”这些关键词优先往一维DP或者贪心上想。先说1143这道题。最长公共子序列和最长公共子数组连续的最大区别在于“是否要求连续”。子序列不要求连续只要求相对顺序一致这就意味着我们在比较两个字符串的某个位置时如果当前字符不匹配不能直接放弃而是要把之前已经匹配到的结果“传递”下来。这个“传递”操作就是二维DP里dp[i][j] max(dp[i-1][j], dp[i][j-1])这行代码的含义。1035不相交的线如果你把两个数组的元素看成是两个平行排列的点列然后匹配相等的元素画线要求线不能交叉那么“不能交叉”的本质就是匹配的元素在两个数组中的相对顺序必须一致。这恰好就是最长公共子序列的定义。所以这道题只需要把字符串换成数组把字符相等换成数值相等代码逻辑一模一样。392判断子序列更简单一些它只要求判断s是否是t的子序列而不是求最长公共子序列的长度。这意味着我们只需要沿着t扫一遍看s的字符能否按顺序全部找到。可以理解为1143的一种特例——如果最长公共子序列的长度恰好等于s的长度那么s就是t的子序列。53最大子序和则是一个经典的一维问题。它不涉及两个序列的比较而是要在单个数组里找一个连续子数组使它的和最大。这个问题的核心思路是每到一个新位置要么把当前元素累加到之前的子数组上要么从当前元素重新开始一个新子数组取两者中的较大值。这样梳理下来你会发现今天四道题其实是在训练两种DP思维二维的比较思维和一维的延续/重置思维。下面我逐一拆解每道题的具体实现。2. 核心细节解析与实操要点2.1 1143. 最长公共子序列二维DP的核心模型这道题的状态定义非常经典dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。这里有个很容易搞混的点——dp[i][j]对应的到底是text1[0..i-1]还是text1[0..i]我习惯用的是前者也就是让 dp 数组的下标从1开始计数这样初始化时dp[0][j]和dp[i][0]都天然是0空字符串和任何字符串的公共子序列长度都是0而且遍历时不需要做大量的下标偏移判断。递推公式分两种情况。情况一text1[i-1] text2[j-1]。此时当前位置的字符匹配上了那么dp[i][j] dp[i-1][j-1] 1。为什么是dp[i-1][j-1]而不是dp[i-1][j]或者dp[i][j-1]因为这两个字符既然相等它们就可以作为公共子序列的最后一个字符前面部分的最佳结果自然就是两个字符串各自去掉当前字符后的最佳结果即dp[i-1][j-1]。情况二text1[i-1] ! text2[j-1]。此时当前字符不匹配但我们不能直接返回dp[i-1][j-1]因为有可能text1的前i-1个字符与text2的前j个字符已经有了更长的公共子序列或者反过来。所以这里取max(dp[i-1][j], dp[i][j-1])。这个操作的本质是“跳过当前不匹配的字符保留之前已经计算出的最优值”。关于遍历顺序二维DP的遍历顺序通常是从上到下、从左到右因为每个dp[i][j]依赖的是dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]这三个方向的值只要保证这三个方向先被计算出来即可。字符串的字符比较用charAt(i-1)而不是charAt(i)是因为 dp 数组的 i 下标从1开始映射到字符串下标时要减1。参考实现如下class Solution { public int longestCommonSubsequence(String text1, String text2) { int m text1.length(), n text2.length(); int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { if (text1.charAt(i - 1) text2.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }时间复杂度O(mn)空间复杂度O(mn)。如果追求空间优化可以用滚动数组把空间降到O(n)因为每一行只依赖上一行和当前行的前一列。不过强烈建议第一遍刷题先写二维的把状态转移想透了再优化。这里还有一个我踩过的坑有些版本的状态定义是dp[i][j]表示以text1[i]和text2[j]结尾的公共子序列长度这种定义下递推公式会变得很别扭因为不匹配时你需要把结果清零最后还要在遍历过程中维护一个全局最大值。初学者很容易被这种定义绕晕。我的建议是牢牢记住“前i个字符”这种前缀型定义它才是最长公共子序列的标准做法。2.2 1035. 不相交的线换个马甲你认识吗这道题拿到手第一反应可能觉得是几何问题或者图论问题但实际上它的核心就是最长公共子序列。为什么我们来看约束条件nums1和nums2各自排列成一行如果两个相同数值的元素连线要求任意两条线不能相交。“不能相交”等价于什么假设我们在nums1中选了位置i1匹配nums2中的位置j1后来又选了位置i2匹配j2如果i1 i2但j1 j2那么这两条线就必然交叉。所以为了保证不相交必须满足nums1中的下标递增时nums2中匹配的下标也必须递增。也就是说匹配的序列在两个数组中的相对顺序完全一致——这正是公共子序列的定义。所以这道题的做法很简单把1143的代码直接改一下字符串换成数组字符比较换成数值比较。class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { if (nums1[i - 1] nums2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }如果你已经理解了1143这道题应该5分钟内能做出来。做不出来也没关系说明你还没有建立“问题抽象”的能力——看到不相交应该立刻联想到顺序一致性再联想到公共子序列。这种能力只能靠多刷题来培养没有捷径。还有一个细节值得注意这题的数字范围没有限制数组里可能出现重复元素。重复元素不影响算法正确性因为我们在比较时只取第一个满足相等条件的位置进入状态转移而最长公共子序列本身允许重复匹配。实测下来重复元素反而会让公共子序列变长这符合直觉。2.3 392. 判断子序列双指针和DP两种解法这道题最简单直接的方法其实是双指针一个指针在s上走一个指针在t上走遇到匹配的字符s指针前进无论匹配与否t指针都前进。如果s指针能走到末尾说明s是t的子序列。时间复杂度O(n)比DP快得多。但既然它出现在动态规划的训练营里我建议你也用DP做法写一遍因为这道题本质上是1143的退化版本——“判断s是否为t的子序列”等价于“s和t的最长公共子序列长度是否等于s的长度”。如果等于说明s的所有字符都能按顺序在t中找到那么s自然是t的子序列。class Solution { public boolean isSubsequence(String s, String t) { int m s.length(), n t.length(); int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { if (s.charAt(i - 1) t.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n] m; } }这里有个很容易踩的坑如果s的长度大于t的长度那么s一定不是t的子序列这个可以直接提前返回false省去不必要的计算。另外如果s是空字符串根据定义空字符串是任何字符串的子序列应该返回true。这两个边界条件在处理输入时值得先判断掉。双指针解法的话代码更简洁也更适合面试时作为第一反应。但DP解法能帮你把这道题和1143联系起来形成一个知识网络。我个人的建议是面试时如果时间紧张直接说双指针解法然后提一句“这道题也可以用最长公共子序列的思路做”展示你对DP模型的理解深度。2.4 53. 最大子序和贪心思维和DP的统一这道题是LeetCode上的经典题目解法很多暴力、分治、DP、贪心。但今天我们要聊的是DP思路。状态定义是dp[i]表示以nums[i]结尾的连续子数组的最大和。注意“以nums[i]结尾”这个限定条件非常重要它保证了子数组是连续的。那么递推公式就是dp[i] max(dp[i-1] nums[i], nums[i])。什么意思当我们处理到第i个元素时有两种选择第一种是把当前元素接到之前的子数组后面形成一个新的子数组和为dp[i-1] nums[i]第二种是从当前元素重新开始一个新子数组和为nums[i]。取两者中的较大值就能保证以当前元素结尾的子数组和最大。class Solution { public int maxSubArray(int[] nums) { int[] dp new int[nums.length]; dp[0] nums[0]; int result dp[0]; for (int i 1; i nums.length; i) { dp[i] Math.max(dp[i - 1] nums[i], nums[i]); result Math.max(result, dp[i]); } return result; } }初始化时dp[0] nums[0]因为以第一个元素结尾的子数组只有它自己。遍历从i1开始同时用一个result变量记录全局最大值因为dp[i]只保证以i结尾的最大值而全局最大值可能出现在任何一个位置。这里我想多说一句关于“为什么不能用dp[i] max(dp[i-1], dp[i-1] nums[i])”这个常见错误。有些初学者会想如果不选当前元素那就延续之前的最大子数组。但问题在于dp[i]的定义是“以 nums[i] 结尾”的子数组如果你不选当前元素那这个子数组就不以 nums[i] 结尾了状态定义就被破坏了。所以正确的做法是要么要当前元素要么从当前元素重新开始没有“不要当前元素”这个选项。那个选项属于全局最大值的范畴由 result 负责维护。这道题的空间可以优化成O(1)用一个变量current维护以当前元素结尾的最大和再用一个变量max维护全局最大值。遍历时不断更新这两个变量即可。这种空间优化的写法也更好背、更好讲class Solution { public int maxSubArray(int[] nums) { int current nums[0]; int max nums[0]; for (int i 1; i nums.length; i) { current Math.max(current nums[i], nums[i]); max Math.max(max, current); } return max; } }这个写法其实和贪心法的思路是一致的如果之前的累积和是负数那么它对后面的贡献是负的不如直接丢弃从当前元素重新开始。current nums[i]与nums[i]取最大值天然就实现了“丢弃负累积”的效果。3. 实操过程与核心环节实现3.1 一题三解从1143到392的思维迁移我在实际刷题时会刻意做“一题多练”的训练。拿今天这四道题来说我建议你的实操流程是先独立做1143然后在不看代码的情况下把1143的代码改写成1035和392。这个过程能帮你检验自己是否真的理解了DP的状态定义和递推公式而不是背代码。具体操作如下完成1143后新建一个代码文件把longestCommonSubsequence函数复制一份改名为maxUncrossedLines。然后把参数类型从String换成int[]把text1.charAt(i-1)换成nums1[i-1]最后把返回值类型保持int不变。如果你能在30秒内完成这个改写说明你对两题之间的关系有了真正理解而不是停留在“听过”的层面。接下来做392时同样从1143出发把返回值改为dp[m][n] m。这里要注意的是392还有一种DP写法是专门用来判断子序列的dp[i][j]表示s的前i个字符是否是t的前j个字符的子序列递推公式变为if (s.charAt(i-1) t.charAt(j-1)) dp[i][j] dp[i-1][j-1]; else dp[i][j] dp[i][j-1];。这种写法更贴合“是否”这个布尔语义但和前一种写法在本质上是一样的。我建议你两种都写一遍感受一下布尔型和数值型状态定义的差异。至于53它和前面三道题的关联性不大放在同一天的训练营里更像是一种“换脑子”的安排。我的实操建议是先自己写一版DP然后再用贪心法写一遍对比两种写法的代码差异。你会发现贪心法其实就是DP空间优化后的形态两者在代码上几乎一样只是在解释上略有不同。DP强调“以当前元素结尾的最大和”贪心强调“丢弃负累积区域”。3.2 DP表的可视化推演很多初学者对DP的理解停留在“套公式”层面一旦遇到变体题目就卡壳。我强烈推荐一个实操技巧手动填表。拿1143举例输入text1 abcde,text2 ace你可以在纸上画一个 6 行 4 列的表格把 dp 数组一行一行地填出来。第一行和第一列全是0空字符串边界。当i1, j1时text1[0]a和text2[0]a相等所以dp[1][1] dp[0][0] 1 1。当i2, j2时text1[1]b与text2[1]c不相等所以dp[2][2] max(dp[1][2], dp[2][1])。手动填完整个表后你会直观地看到 dp 数组中数字的走向匹配时数字沿对角线递增不匹配时数字从上方或左方“复制”过来。这种视觉记忆比单纯看代码要牢固得多。对于53同样可以手动模拟nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]手动计算每一轮的current和max。你会发现当current变成负数时下一轮就果断抛弃它从新元素重新开始。这个负值丢弃机制也是面试官最爱追问的点——为什么current为负时要重置因为负值无论加上哪个数都会让那个数变小与其保留它不如从当前数开始。3.3 复杂度分析和边界条件梳理今天四道题的复杂度需要分清楚1143和1035时间O(mn)空间O(mn)可优化O(n)。这类题的最优时间复杂度就是O(m*n)因为你要比较两个序列中的每一对元素。392双指针解法时间O(n)空间O(1)。DP解法时间O(m*n)空间O(n)优化后。面试时优先说双指针解法。53一维DP时间O(n)空间O(n)可优化O(1)。分治法也可以做到O(n)时间但编码复杂度更高不推荐在面试中使用。边界条件的常见坑我也整理一下1143两个字符串都为空时返回0。一个为空时也返回0。1035数组为空时返回0。注意数组长度可能为0代码里循环直接跳过即可。392s为空时返回truet为空且s不为空时返回false。53数组只有一个元素时返回该元素本身。数组元素全是负数时最大子序和就是最大的那个负数。这些边界条件看起来简单但我在实际面试中见过不少候选人在空数组上栽跟头——不是没判空就是没想清楚空数组的返回值应该是什么。写代码前花10秒钟想一遍边界能避免很多低级错误。4. 常见问题与排查技巧实录4.1 一维DP和二维DP的越界问题二维DP最经典的越界问题出现在dp[i-1][j-1]这种访问上。如果你把 dp 数组初始化为new int[m][n]而不是new int[m1][n1]那么当i0或j0时访问dp[-1][-1]就会直接越界。解决办法是两种要么像我前面写的那样把 dp 数组扩一圈用m1和n1的尺寸这样 i 从1开始遍历就不会越界要么在循环里额外判断i 0 j 0。我强烈推荐前者因为后者会让代码变得啰嗦而且容易漏判断。还有一个细节初始化时 Java 的 int 数组默认值是0正好省去了为第一行和第一列赋0值的操作。如果你是 C 选手用vectorvectorint dp(m1, vectorint(n1, 0))也能达到同样的效果。Python 的话要注意列表推导式的写法dp [[0] * (n1) for _ in range(m1)]千万别写成[[0] * (n1)] * (m1)后者会让所有行共享同一个列表对象改一个值全部跟着变我见过太多人踩这个坑了。4.2 子序列 vs 子数组/子串连续性的区别“子序列”“子数组”“子串”这三个概念我在面试中几乎每次都会被问到也是 DP 题目里最容易混淆的地方。子序列不要求连续只要元素在原序列中的相对顺序不变即可。比如[1, 3, 5]是[1, 2, 3, 4, 5]的子序列。子数组/子串要求连续。比如[2, 3, 4]是[1, 2, 3, 4, 5]的子数组但[1, 3, 5]不是。这两者在 DP 递推公式上的直接体现是子序列问题在不匹配时使用max(dp[i-1][j], dp[i][j-1])来保留历史结果而子数组问题在不匹配时需要重置为0。你可以对比1143和718最长重复子数组这两道题会发现后者在nums1[i-1] ! nums2[j-1]时直接dp[i][j] 0这就是连续性和非连续性的本质差异。理解了这个差异你在做题时就能快速判断如果题目要求连续那么当前状态只能由“前一个位置匹配成功”转移过来不匹配就断掉如果题目不要求连续那么之前积累的结果可以跨过不匹配的位置继续传递。4.3 最大子序和的负数数组陷阱53题的一个经典易错点是数组全为负数时dp[i-1] nums[i]永远小于nums[i]所以current每轮都会重置为nums[i]最终max会是数组中最大的负数。这个逻辑是正确的但很多人在写初始化时会犯错如果把max初始化为0那么全负数数组会错误地返回0而不是最大的那个负数。正确做法是把max初始化为nums[0]或者初始化为Integer.MIN_VALUE。第一版代码里我用的是nums[0]初始化这样数组只有1个元素时也无需特判。如果你习惯用Integer.MIN_VALUE初始化一定要在循环前先处理第一个元素或者从0开始遍历。另外如果你用分治法解53面试时可能被追问“为什么分治法的时间复杂度是 O(n) 而不是 O(n log n)”。这个问题其实有点绕分治法每层都要线性扫描跨越中点的最大子数组但每层的总扫描长度是 n递归深度是 log n所以总复杂度是 O(n log n)。有些资料说 O(n) 是因为他们用了某种优化但标准分治法实现就是 O(n log n)。在面试中如果没把握建议直接用 DP 或贪心讲分治法可以作为“我还会其他方法”的加分布置。4.4 练习时的输出调试技巧调试 DP 题目时最常见的手段是打印 dp 数组。Java 里两层循环打印即可Python 可以用for row in dp: print(row)JavaScript 用console.table(dp)会直接输出一个表格非常直观。我个人的习惯是写完一道 DP 题后找一个简单的小样例手动跑一遍把 dp 表打印出来核对每一格的值。比如 1143 的样例abcde和ace最终 dp 表右下角应该是3。如果你打印出来的表有不符合预期的值就从第一个不符合的位置往前推检查是状态定义错了还是递推公式写错了。这种调试方式比单步断点调试更高效因为 DP 的问题通常是整体性的——某个方向的值传错了会导致后面一连串的错。肉眼扫一遍表格往往很快就能定位问题在哪里。5. 从刷题到面试的复盘心得把今天的四道题做完后我建议你做一次“复盘式总结”而不是急着刷下一批题。复盘的核心不是“我AC了”而是“如果明天面试官让我讲这题我能讲清楚什么”。拿1143举例一个合格的面试回答应该包含状态定义dp[i][j]表示前i/前j的最长公共子序列长度、为什么这样定义前缀型定义便于处理空字符串边界、递推公式的推导匹配与不匹配两种情况、复杂度分析时间O(mn)、空间可优化、边界条件空字符串。如果你能在5分钟内把这些讲完比闷头刷10道题更有价值。从知识网络的角度看今天的四道题可以帮你串联起一类模型两个序列的匹配问题用二维DP一个序列的最优分段问题用一维DP。前者如编辑距离、正则表达式匹配、通配符匹配后者如打家劫舍、买卖股票的最佳时机。当你刷到这些题时会发现它们和今天的题在状态转移的思路上有很强的相似性。我个人在刷完这组题后的一个体会是DP不做出来不丢人做不出来但能说出“这题应该用二维DP状态是dp[i][j]但我还没想清楚递推”也比完全没有思路强。面试官考察的核心不是你能不能当场AC而是你有没有框架性的思考能力。今天这四道题恰好能帮你建立这个框架——1143给你二维DP的标准范式1035训练抽象能力392训练退化思维53训练一维DP的延续与重置。把这四道题吃透后面再遇到序列类DP题目你的第一反应会快很多。另外说一个实操层面的建议刷题时不要只写一种语言的解法。我在训练营里通常用 Java 写第一遍然后隔天用 Python 重新写一遍同款题。语言切换的过程会强迫你重新思考逻辑结构而不是依靠肌肉记忆敲代码。这个方法亲测有效推荐你也试试。