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]，因为以第一个元素结尾的子数组只有它自己。遍历从i=1开始，同时用一个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（空字符串边界）。当i=1, j=1时，text1[0]='a'和text2[0]='a'相等，所以dp[1][1] = dp[0][0] + 1 = 1。当i=2, j=2时，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，代码里循环直接跳过即可。
- 392：s为空时返回true，t为空且s不为空时返回false。
- 53：数组只有一个元素时，返回该元素本身。数组元素全是负数时，最大子序和就是最大的那个负数。
这些边界条件看起来简单，但我在实际面试中见过不少候选人在空数组上栽跟头——不是没判空，就是没想清楚空数组的返回值应该是什么。写代码前花10秒钟想一遍边界，能避免很多低级错误。
4. 常见问题与排查技巧实录
4.1 一维DP和二维DP的越界问题
二维DP最经典的越界问题出现在dp[i-1][j-1]这种访问上。如果你把 dp 数组初始化为new int[m][n]而不是new int[m+1][n+1]，那么当i=0或j=0时，访问dp[-1][-1]就会直接越界。解决办法是两种：要么像我前面写的那样，把 dp 数组扩一圈，用m+1和n+1的尺寸，这样 i 从1开始遍历就不会越界；要么在循环里额外判断i > 0 && j > 0。我强烈推荐前者，因为后者会让代码变得啰嗦，而且容易漏判断。
还有一个细节：初始化时 Java 的 int 数组默认值是0，正好省去了为第一行和第一列赋0值的操作。如果你是 C++ 选手，用vector<vector<int>> dp(m+1, vector<int>(n+1, 0))也能达到同样的效果。Python 的话要注意列表推导式的写法：dp = [[0] * (n+1) for _ in range(m+1)]，千万别写成[[0] * (n+1)] * (m+1)，后者会让所有行共享同一个列表对象，改一个值全部跟着变，我见过太多人踩这个坑了。
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 重新写一遍同款题。语言切换的过程会强迫你重新思考逻辑结构，而不是依靠肌肉记忆敲代码。这个方法亲测有效，推荐你也试试。
)
