第43天，代码随想录算法营正式进入子序列动态规划的深水区。今天的四道题是1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列。前两题是标准的二维DP，第三题是经典的一维DP，第四题则是“最长公共子序列”的退化版本。一天刷下来，最大的感受是：子序列类DP的边界条件才是最考验人的地方，很多思路看起来顺理成章，但真正落到dp数组的递推上，稍不留神就会写出一个能通过样例、却经不起推敲的解。
如果你正在刷代码随想录，或者正处于动态规划专项的中期，这四道题值得放在一起反复咀嚼。它们彼此之间有很强的递进关系：1143是基础模板，1035是模板的换皮，392是模板的特殊情形，53则是另一个维度的一维DP。把这几题的异同点理清楚，比单独刷十道不相关的DP题都有用。
1. 为什么这四道题适合放在同一天消化
我最初看到当天的题单时，其实有点疑惑：1143和1035明显是亲兄弟，392看起来也逃不出1143的框架，但53“最大子序和”混进来，画风不太一样。刷完才明白，这四道题刚好覆盖了子序列DP里最常见的三类状态设计思路：“二维前缀DP”“一维结尾DP”“贪心取最优位置”。
先说1143、1035、392这一组。它们本质上都在做同一件事：判断或计算两个序列之间按顺序匹配能达到的最大效果。区别只在于最终要问的是什么：1143问最长公共子序列的长度，1035问最多能画出多少条不相交的线，392问较短的字符串能不能完整出现在较长的字符串里。这三题的递推公式长得很像，但“为什么这么递推”的解释角度完全不同。1035如果没有意识到它等价于最长公共子序列，很容易陷入几何相交性的泥潭；392如果只会双指针，就体会不到它在DP框架里的独特地位。
再看53。它是一个一维数组上的子序列问题，但“连续”这个限制让它的状态定义和前面的题完全不同。前面三题的状态都是“两个序列各看到前几位”，而53只需要一个“以当前元素结尾”的局部状态。它不复杂，但它能帮你认清一个容易被忽略的事实：DP的状态不一定非得是“从头到当前位置的整体结果”，也可以是“强制包含当前位置的结果”。这个区别，在处理很多后续题目时特别关键。
所以这一天的题单设计得很好：先用二维DP建立“子序列匹配”的直觉，再用一个一维题打破你对状态定义的固有认知，最后用392让你回头重新审视第一道题，发现同一个模板可以被简化到什么程度。
2. 1143. 最长公共子序列：先搞定最标准的二维DP
2.1 状态定义：dp[i][j]到底代表什么
很多人在写1143时一上来就定义dp[i][j]表示“text1的前i个字符和text2的前j个字符之间的最长公共子序列长度”。这个定义本身没问题，但要注意它隐含了一个偏移：i=0或j=0都代表空字符串，所以实际比较字符时用的是text1[i-1]和text2[j-1]。
为什么非要这样偏移？因为动态规划的边界必须覆盖空串的情况。如果不偏移，dp[0][0]会变成“第一个字符和第一个字符的最长公共子序列”，空串的边界无法表达，最终初始化会非常别扭。偏移一位之后，dp[0][j]=0和dp[i][0]=0的意义很清楚：某一方为空，公共子序列长度只能是0。
状态定义想清楚之后，整个递推就顺理成章了。
2.2 转移方程：为什么相等时加一，不相等时取max
当text1[i-1] == text2[j-1]时，说明当前这两个字符可以拼接到已经匹配好的公共子序列尾部，所以：
dp[i][j] = dp[i-1][j-1] + 1
这里有个容易纠结的点：为什么不是max(dp[i-1][j], dp[i][j-1]) + 1？因为如果这两个字符相等，它们可以同时成为公共子序列的最后一个字符，而dp[i-1][j-1]已经天然包含了“前面所有可能的最优匹配”，直接加1就是最优解。如果再去比较dp[i-1][j]和dp[i][j-1]，反而可能重复计算字符，甚至破坏子序列的顺序性。
当两个字符不相等时，情况就不同了。text1[i-1]和text2[j-1]不可能同时作为公共子序列的末尾，所以只能选择其中之一跳过：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[i-1][j]的含义是“text1的前i-1个字符和text2的前j个字符的最长公共子序列”，相当于把text1[i-1]这个字符丢弃；dp[i][j-1]则是丢弃text2[j-1]。取两者的最大值，就能保证在“当前字符不匹配”时，我们的结果不会倒退。
def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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[m][n]这个代码结构就是整个子序列二维DP的基础模板，后面两道题基本上是在这个模板上做减法或换说法。
2.3 和“最长公共子串”的区别要单独拎出来
很多人会把1143和“最长公共子串”混在一起，两者虽然看起来只差“连续”两个字，但转移方程完全不同。公共子串要求字符在原始字符串里连续出现，所以一旦不匹配，长度就要清零；而公共子序列允许中间跳过字符，不匹配时只需要取前面的最大值继续传递。
放在生活场景里理解：子序列像“保留顺序的交友匹配”，你可以跳过不喜欢的人；子串像“必须站在一起的朋友”，一旦中间有人走开，组合就断了。1143这种“可以跳”的性质，是后面1035“不相交的线”能够转化的关键前提。
3. 1035. 不相交的线：一个让你重新认识LCS的改编题
3.1 题目描述里的几何，只是伪装
1035的题目给了一个很形象的场景：两个数组上下排列，把相等的数字连成线，求最多能连多少条线，且线不能交叉。
第一次看到这个题时，我的第一反应是考虑线段的几何性质，甚至想用区间重叠来判断。真正动手之后才发现，这题根本没有所谓的几何逻辑，它彻头彻尾就是1143最长公共子序列。
为什么？因为“连线不相交”等价于“两条线对应的下标在两个数组里都保持递增顺序”。你在nums1中选了某个下标的数字，又在nums2中选了对应数字，两条线如果相交，就意味着至少有一对匹配的先后顺序发生了反转。换句话说，一组不相交的线，恰好就是两个数组的一个公共子序列。那要求“最多不相交的线”，自然就是求最长公共子序列的长度。
想通这一点之后，连代码都几乎不用改。把1143里的两个字符串换成两个数组即可：
def maxUncrossedLines(nums1, nums2) -> int: m, n = len(nums1), len(nums2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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[m][n]3.2 为什么相等时加一，不相等时取max
如果只停留在“抄代码”的层面，这道题就浪费了。它真正的价值是帮你建立一种“问题转化”的直觉：凡是让你匹配两个序列、且限制条件与顺序相关，不妨先想想能不能归约成公共子系列。
1035里的“不相交”实际上是一个非常强的顺序约束。任何交点，本质上是在说：原本在前面的匹配，在另一个数组里反而落到了后面。这不就是子序列顺序被打破了吗？所以只要把“线不相交”翻译成“选出的下标序列在两边都单调递增”，答案就浮出水面了。
3.3 用一个状态图辅助理解递推
如果递推导不明白，可以画一个m+1行n+1列的表格。从左到右、从上到下填数，规则只有两条：当前数值相同时，取左上角加一；不相同时，取上方和左方的较大值。
我刷这道题时特意对照1143在表格上多填了两遍。最后总结出一个记忆点：二维子序列DP里，dp[i][j]永远是“已考虑的前缀”层面的结果，而不是“恰好以某个字符结尾”的结果。所以即使最后两个字符不匹配，前面的最优结果也能完全保留下来，不会像公共子串那样断掉。
如果你能把这个点彻底想清楚，后面再做编辑距离、正则匹配之类更复杂的字符串DP，会轻松不少。
4. 53. 最大子序和：一维DP也值得讲透
4.1 状态定义：以nums[i]结尾，而不是前i个元素
53题太经典了，以至于很多人直接背Kadane算法：遍历数组，维护一个当前和，如果当前和变成负数就重置为0，过程中记录最大值。这个贪心做法是对的，但在算法营里，我更推荐先写DP版本，因为只有理解了状态定义，才能真正明白“为什么负数要重置”。
DP版本的状态定义很特别：
dp[i]表示“以nums[i]为结尾的连续子数组的最大和”。
注意，这里不是“前i个元素的最大子数组和”。如果定义成后者，递推会比较别扭，因为你不知道前面那个最大子数组到底在哪儿结束，也就不知道能不能接上nums[i]。而定义成“以当前元素结尾”之后，转移变得非常清晰：
dp[i] = max(nums[i], dp[i-1] + nums[i])
这个式子的含义是：要么从nums[i]重新开始一个新的子数组，要么把nums[i]接到前面的最优子数组后面。二者取较大值。
4.2 为什么“从nums[i]重新开始”的条件是nums[i]本身
很多教材把转移写成dp[i] = max(dp[i-1] + nums[i], nums[i])，二者完全等价。但真正理解它，需要想清楚一个反直觉的点：为什么不是max(dp[i-1], dp[i-1] + nums[i])？
因为dp[i]必须包含nums[i]。题目要求连续子数组，而且状态定义强制以nums[i]结尾。如果取dp[i-1]，得到的子数组根本不含nums[i]，就没有意义。这也是为什么dp[i]并不是最终答案，最终答案是max(dp)—— 因为最优子数组可能结束在任意位置。
def maxSubArray(nums) -> int: dp = [0] * len(nums) dp[0] = nums[0] result = nums[0] for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i - 1] + nums[i]) result = max(result, dp[i]) return result更进一步，因为dp[i]只依赖dp[i-1]，所以可以只用一个变量滚动更新：
def maxSubArray(nums) -> int: cur = nums[0] result = nums[0] for i in range(1, len(nums)): cur = max(nums[i], cur + nums[i]) result = max(result, cur) return result这个滚动版本就是大家常说的Kadane算法，只不过很多人只记住了“和为负就重置”，没有意识到它背后的状态含义。
4.3 一个很容易踩的坑：把dp[i]当成全局最优
我当初做这题时卡了很久，因为我始终试图把dp[i]定义成“前i个元素的最大子序和”，然后递推时发现nums[i]不知道该不该加进去。如果前一个最优子数组的结束位置不在i-1，那强行把nums[i]加上去就破坏了连续性。
这个纠结恰恰说明，“以当前元素结尾”这个强制条件不是可有可无的。它牺牲了一点“全局感”，换来了递推时的无后效性。动态规划里的“无后效性”这个词，在53这道题上体现得最直观——你根本不需要关心之前的子数组是从哪里开始的，只需要知道以i-1结尾的最优和是多少。
5. 392. 判断子序列：双指针解法与“简化版LCS”的DP写法
5.1 双指针解法为什么有效
392问的是，字符串s是不是字符串t的子序列。最朴素的想法是用双指针：一个指针遍历s，另一个遍历t，每当在t中找到s当前字符，就移动s的指针，然后将t的指针继续向后。
def isSubsequence(s: str, t: str) -> bool: i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)这个做法之所以正确，是因为一个贪心性质：匹配s的字符时，能匹配则匹配，且匹配位置越靠前越好。因为在t中越早匹配，后续可用的字符范围就越大，永远不会让结果变差。如果这种“尽早匹配”的策略都找不到完整子序列，那换用任何延迟匹配的策略也不可能成功。
5.2 从1143的视角看：判断子序列其实是LCS的特例
如果只教双指针，这题几分钟就结束了。但放在“最长公共子序列”这一天的题单里，你必须学会从DP视角再解一次。
回忆1143的递推：
- 字符相等时
dp[i][j] = dp[i-1][j-1] + 1 - 字符不等时
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
对于判断子序列来说，因为我们要判断s能不能完整出现在t中，所以s的每个字符都必须被匹配。这意味着，当s[i-1] != t[j-1]时，我们只能选择“跳过t中的当前字符”，而不能选择“跳过s中的当前字符”。于是转移简化为：
dp[i][j] = dp[i][j-1]
最终，如果dp[m][n] == len(s)，说明s被完整匹配了。写成代码：
def isSubsequence(s: str, t: str) -> bool: m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = dp[i][j - 1] return dp[m][n] == m当然，这个DP版本的复杂度是O(mn)，远不如双指针的O(n)。但它的意义在于让你看到，1143的模板稍作改动，就能覆盖一类“少了一个自由度”的问题。以后遇到更复杂的变体时，你不会因为没接触过而手足无措。
5.3 进阶思路：预处理t的每个字符位置
LeetCode的392还有一道进阶题：如果输入中有大量s，每个s都要判断是不是t的子序列，怎么优化到 O(len(s) * 某种常数) 级别。
这就是经典的“记忆化后续位置”问题。你可以预处理t，建立一个二维数组next_pos[j][26]，表示从t[j]这个位置开始，每个字母下一次出现的位置。之后对于任意一个s，直接在预处理表里跳着找字符即可。
虽然这道题的进阶版本不一定在算法营里出现，但如果你已经吃透了392的DP写法，理解这个预处理思路会变得非常自然：它本质上还是“顺序匹配”，只是把查找效率从线性扫描变成了O(1)跳转。
6. 四题连做之后的三个关键复盘
6.1 复盘一：二维子序列DP的“跳过”是怎么在转移里实现的
很多人会把1143的不相等转移公式记成“取max”，但不知道取max到底在干什么。其实dp[i-1][j]代表“跳过text1的当前字符”，dp[i][j-1]代表“跳过text2的当前字符”。
如果你能把这个“跳过”的动作具象化，1035和392都不再需要背公式。1035的不等转移和1143一模一样，因为它可以从两个数组里任意跳；392的不等转移只剩下“跳过t”，因为s的字符不能被跳过，否则s就不是完整匹配的子序列了。
6.2 复盘二：“不相交”类问题的识别技巧
1035的价值在于问题转化。以后看到“两个序列连线”“配对但不能交叉”“保持相对顺序”这类描述时，第一反应应该是公共子序列。
这个识别过程完全可以靠平时训练积累。我在做完1035之后，特意把LCS、编辑距离、最长递增子序列这几个题的题干放在一起对比。它们都有一个共同特征：要求在保持原有顺序的前提下做匹配。不同点只是“匹配的代价和奖励规则”。掌握这层共性之后，再遇到新的字符串DP，你的第一反应就不再是背模板，而是思考“这题比标准LCS多了什么限制或少了什么选择”。
6.3 复盘三：53的“结尾状态”是很多数组DP的基础
最后再回到53。很多人觉得它简单，随手写出Kadane算法，然后就过了。但如果我把这题改成“返回最大子数组的起始和结束下标”，你能立刻改出来吗？
如果理解了dp[i]是“以 i 结尾”的最优子数组，而最终答案是max(dp)，那么只要在更新最大值的同时记录当前子数组的起止位置，就能轻松扩展。这个“结尾状态”的建模方式，在后面股票买卖类问题、打家劫舍类问题里还会反复出现。它和1143的“前缀状态”是两种完全不同的建模视角，但都极其常用。
今天这四道题刷下来，最值得做的收尾工作不是看题解，而是合上代码，在纸上默写每个题的转移方程，并写出每个方程对应“跳过了哪个字符、保留了哪个前缀”。能无卡顿地写出来，才算把这一天的内容真正消化了。
