1. 题目一句话定位四道题其实是一条DP主线先说结论第四十九天的四道题本质上是一条动态规划主线上的四个台阶。1143最长公共子序列是地基1035不相交的线和392判断子序列都是它的变形只是换了层皮53最大子序和则是另一条分支属于一维DP的经典入门模型。把这几道题放在同一天消化其实是在帮我们打通“二维DP表格怎么填”和“一维DP状态怎么压缩”这两个核心能力。我刷题的习惯是先把题目按考察点归类再去找题目之间的递进关系。四道题如果散着刷很容易刷一道忘一道但如果你能看到它们共享的底层逻辑刷完一遍基本就能形成长期记忆。这一天的题单设计得很有节奏感先做1143理解“基于两个序列的二维DP”再做1035发现“换了个题目背景但状态转移一模一样”再做392发现“原来只是1143的一个特殊case”最后用53切换一下思维从二维回到一维练一下“最大子序和”这种更基础的DP模型。这个顺序我建议不要打乱。很多人在训练营里容易犯的毛病是挑软柿子捏——先做53最大子序和因为它看起来最简单但这样一来你在做1143的时候反而缺少从“一维思维”升级到“二维思维”的铺垫。跟着题单顺序走每道题都是在上一道题的基础上加一点点新东西理解成本是最低的。2. 最长公共子序列1143二维DP的核心模板2.1 为什么不能用滑动窗口或者双指针拿到1143这道题很多人第一反应是“这不就是求两个字符串的公共子串吗用双指针或者滑动窗口不就行了”这里必须先纠一个概念子序列和子串是两回事。子串要求字符在原字符串中连续而子序列只要求保持相对顺序字符之间可以跳过。比如abcde和ace公共子序列是ace但公共子串最长只有1。滑动窗口和双指针擅长处理“连续”的问题一旦允许跳着匹配它们就无能为力了。从另一个角度看这道题是“求两个序列的最长公共子序列”也就是经典的LCS问题。它天然具有“两个维度同时变化”的特征所以不能用一维DP硬套必须用一个二维dp[i][j]来表示“考虑了第一个字符串的前i个字符、第二个字符串的前j个字符时能得到的LCS长度”。二维DP表格这个思想是后面所有同类题目的根基。2.2 dp数组的定义与递推公式的推导逻辑定义dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。这里有一个新手容易纠结的点为什么是前i个字符而不是以第i个字符结尾因为子序列不要求连续如果定义成“以i结尾”我们在状态转移时会丢失“前面已经跳过了一些字符”的信息导致无法处理跳跃匹配的情况。而定义成“前i个字符”每次决策只需要关注当前字符text1[i-1]和text2[j-1]是否相等剩下的交给之前的状态这样既简洁又完备。递推公式分两种情况我再用自己的话翻译一遍因为这是全题的核心当text1[i-1] text2[j-1]时说明当前这两个字符可以配对那么dp[i][j] dp[i-1][j-1] 1。这里为什么是dp[i-1][j-1]而不是max(dp[i-1][j], dp[i][j-1]) 1因为这两个字符一旦配对它们就不能再和各自前面的其他字符配对了所以只能在“两个串都退一格”的基础上加1。这是LCS问题的经典结论也是和“编辑距离”类问题最大的区别点。当text1[i-1] ! text2[j-1]时当前这两个字符不能配对那么dp[i][j]应该取max(dp[i-1][j], dp[i][j-1])。这个转移的含义是要么放弃text1的第i个字符让它不参与匹配看看text1[0..i-2]和text2[0..j-1]的LCS是多少要么放弃text2的第j个字符看看另一个方向是多少。取两者最大值就是当前状态的最优解。2.3 初始化与遍历顺序的细节初始化方面dp[0][j]和dp[i][0]都应该是0因为任何一个字符串的前0个字符和另一个字符串的任何前缀的公共子序列长度都是0。这个初始化的意义在于为递推提供“空串”边界。遍历顺序我习惯用双层循环外层遍历text1内层遍历text2从1开始到各自长度为止。为什么不用从0开始因为dp[0][j]和dp[i][0]已经是初始值了从1开始遍历可以让dp[i-1][j-1]等状态在访问时已经计算完毕不会出现访问未初始化状态的问题。这里分享一个我踩过的坑有些版本会定义dp[i][j]表示以text1[i]和text2[j]结尾的LCS长度这种定义在求“最大长度”时需要在每次更新时维护一个全局最大值而且递推时还需要判断前一个状态写起来会更绕。建议直接记住“前i个字符”这个定义它和“子序列不要求连续”的特性是天然匹配的。// C版本参考实现 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n text1.size(), m text2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; 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[n][m]; } };如果对空间敏感可以将二维数组压缩成两行甚至一行。两行版本就是dp[2][m1]滚动使用一行版本需要从右向左更新内层循环因为dp[i-1][j-1]对应的是旧行的左上角值如果从左向右更新会被覆盖。不过初学阶段建议先把二维版本写熟练再考虑优化否则很容易写出bug。3. 不相交的线1035看穿题目伪装LCS换了个马甲3.1 从“连线”问题还原到LCS本质1035这道题题目描述看似复杂——在两条水平排列的数字序列之间连线要求线不相交求最多能画多少条线。第一次看到这个题我脑子里冒出来的是“图论里的最大匹配”甚至想过去做拓扑排序但仔细一想就发现完全不是那么回事。关键洞察在于如果连线的两个数字下标分别是(i1, j1)和(i2, j2)那么这两条线不相交的充要条件是i1 i2时一定有j1 j2或者反过来也就是说连线的两个序列下标必须保持“同步递增”的关系。这本质上就是要求我们在两个序列中找出一个“下标顺序一致”的最长匹配序列——这不就是最长公共子序列吗所以这道题的解法就是把两个数组当作两个序列求它们的最长公共子序列长度。代码写起来和1143几乎一模一样只是把text1[i-1]变成nums1[i-1]text2[j-1]变成nums2[j-1]。3.2 实操对照代码只需改三处当我实际在训练营里做这道题时我把1143的代码直接粘了过来改了三个地方就通过了函数名和参数类型从string改成vectorint变量名从text1、text2改成nums1、nums2比较语句text1[i-1] text2[j-1]改成nums1[i-1] nums2[j-1]。除此之外dp数组的定义、初始化、双层循环、递推公式全部原封不动。这个现象其实揭示了DP题的一个规律题目背景可以千变万化但只要能识别出“两个序列按顺序匹配”这个模式就可以套用同一套DP框架。3.3 为什么要强调“映射同等类型”而不是“值相等”这里有一个细节值得展开1143比较的是两个字符串中的字符是否相等1035比较的是两个数组中的数字是否相等两者在编程上没有任何区别都是基础的比较。但如果题目把数组元素换成对象、结构体你需要自定义“相等”的语义——比如两个对象的某个字段相等就算匹配。这时候你就能体会到DP的核心是“匹配规则”而不是具体的匹配对象。理解到这一层以后遇到“最长重复子数组”、“两个字符串的删除操作”等题目时你就知道如何灵活变换了。4. 判断子序列392LCS的简化场景双指针也能解4.1 题目本质一个序列是否是另一个序列的子序列392题要求判断s是否是t的子序列。换句话说s和t的最长公共子序列长度是否等于s的长度。如果相等说明s的每个字符都能按顺序在t中找到位置那么s就是t的子序列。所以这道题最直接的DP做法就是求dp[n][m]然后判断dp[n][m] s.size()。但这里有一个更高效的思路这道题是LCS的特殊case因为s整体必须被匹配不存在“跳过s中的某个字符”的选项。所以递推公式可以简化不需要维护“放弃s中字符”的情况。也就是说DP时可以只在一个方向上做“放弃”决策当s[i-1] ! t[j-1]时我们应该放弃的是t的第j个字符而不是s的第i个字符即dp[i][j] dp[i][j-1]。只有当s[i-1] t[j-1]时才有dp[i][j] dp[i-1][j-1] 1。如果你把1143的代码直接套过来也能AC因为当s是t的子序列时max(dp[i-1][j], dp[i][j-1])在数值上就等于dp[i][j-1]因为dp[i-1][j]不会更大。但理解这个简化的递推有助于你看到“约束条件变强时DP状态如何随之精简”。4.2 双指针解法与DP解法的对比这道题还有一个线性解法双指针。初始化i0, j0遍历t每当t[j] s[i]时i最后判断i是否等于s.size()。这个做法的正确性在于要判断一个序列是不是另一个序列的子序列贪心地“能匹配就匹配”一定不会错过答案。这个结论看起来显然但严格证明需要用到“子序列匹配中越早匹配越有利”的交换论证。我自己的建议是面试时如果只考这一道题双指针是最高效的但如果是在训练营阶段建议用DP解一次因为这道题的DP写法是理解“最长公共子序列”的极佳过渡材料——从二维DP到一维DP的思维过渡。另外很多变种题比如“判断子序列的个数”、“不同子序列”都是基于这个DP思路扩展的双指针就没法扩展了。DP参考实现class Solution { public: bool isSubsequence(string s, string t) { int n s.size(), m t.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] dp[i][j - 1]; // 关键区别只跳过t的字符 } } } return dp[n][m] n; } };5. 最大子序和53一维DP的经典题贪心也能过5.1 为什么这道题和前面三题放在一起前面三道题都是二维DP核心状态是“两个序列各考虑了多少个字符”而53最大子序和是一维DP核心状态是“以某个位置结尾的子数组的最大和”。把这道题放在同一天看起来有点突兀但其实是训练营刻意设计的“思维切换点”——前一天你还在二维表格里填数字现在要回到一维数组里做决策这种反复横跳的过程能有效强化你对“DP状态定义”的敏感度。5.2 状态定义和转移的两种写法定义dp[i]表示以nums[i]结尾的连续子数组的最大和。这里的关键词是“以nums[i]结尾”——这意味着这个子数组必须包含nums[i]而它可以从nums[i]自己开始也可以从之前的某个位置延续过来。递推关系dp[i] max(nums[i], dp[i-1] nums[i])。这个公式的含义是要么从nums[i]重新开始一个新子数组要么把nums[i]接在之前的最优子数组后面。取两者较大值即为以nums[i]结尾的最大子序和。最终答案不是dp[n-1]而是所有dp[i]的最大值因为最大子数组可能以任意位置结尾。另一种更简洁的写法是不用数组只维护一个cur表示当前前缀的“潜力值”再维护一个maxSum记录全局最大。遍历时不断更新class Solution { public: int maxSubArray(vectorint nums) { int cur 0, maxSum INT_MIN; for (int num : nums) { cur max(num, cur num); maxSum max(maxSum, cur); } return maxSum; } };这个写法本质上是贪心如果当前累积和是负数那么它对后续子数组没有正贡献还不如直接放弃从当前元素重新开始。很多人把这个叫“Kadane算法”其实它和DP是同一个思路的两种表现形式。5.3 一个容易忽略的易错点全负数数组如果nums全是负数比如[-1, -2, -3]很多人的代码会出错因为初始化maxSum 0会导致答案是0而不是-1。正确做法是把maxSum初始化为INT_MIN或者在更新前先取maxSum nums[0]遍历从i1开始。另外我见过有人写出cur max(cur num, 0)这样的代码这在大数组里有正有负时可能也能过但在全负数情况下会错误地输出0。记住最大子序和必须是数组中的一个连续子数组不能为空。所以不能默认空子数组的和为0除非题目明确允许返回0。6. 四道题横向对比状态定义、转移方程与实现要点速查四道题做完整理一下你会发现它们的DP定义虽然形式不同但背后有一个共同的方法论找状态时先问两个问题——“我需要知道哪些信息才能做决策”以及“这些信息能否从前面的状态推导出来”我整理了一张速查表方便你复习时快速回忆题目状态定义相等/匹配时不相等/不匹配时空间优化方式1143 最长公共子序列dp[i][j]: text1前i个字符与text2前j个字符的LCSdp[i-1][j-1]1max(dp[i-1][j], dp[i][j-1])两行滚动 / 一行倒序1035 不相交的线dp[i][j]: nums1前i个与nums2前j个的LCS同上同上同上392 判断子序列dp[i][j]: s前i个是否为t前j个的子序列匹配长度dp[i-1][j-1]1dp[i][j-1]只跳过t可压缩53 最大子序和dp[i]: 以nums[i]结尾的最大子数组和不适用不适用常数空间这个表格的价值在于你可以直观看到“哪些题是同一个模板哪些题需要单独处理”。1143和1035基本就是同一道题392是在1143的转移上砍掉一个分支53则是完全不同的状态定义。把它们放在一起对比记忆比单独刷四道题印象要深刻得多。7. 常见问题与排查技巧实录7.1 “答案比预期大1”的诡异问题做1143时有人会遇到正确答案比预期大1的情况。排查后发现问题往往出在dp数组的维度上——应该是(n1) x (m1)但写成了n x m。为什么会大1因为当i1, j1时如果text1[0] text2[0]正确结果应该是dp[0][0] 1 1。而如果dp数组是n x mdp[0][0]可能是未初始化的随机值导致结果异常。解决方法是初始化dp数组时要确保所有dp[i][0]和dp[0][j]都为0并且数组尺寸要包含0索引。7.2 “不相等分支忘了取max”的低级错误这个错误在1143中非常常见。很多人能写出“相等分支”但到了“不相等分支”就直接写dp[i][j] dp[i-1][j]心想“那就先跳过text1的字符呗”结果答案偏小。正确的max(dp[i-1][j], dp[i][j-1])其实包含了两种跳法——既可以跳过text1的字符也可以跳过text2的字符。只写一个相当于强制规定了“只能从某个方向跳”自然就漏掉了某些可能的匹配。我在实际调试时发现一个规律如果代码总是输出min(n, m)那说明你写成了“最长公共子串”的逻辑连续匹配如果输出比正确答案小多半是“不相等分支”没取max。7.3 53题的“全局最大初始化为0”陷阱所有刷过53的人几乎都踩过这个坑全负数数组情况下输出0而非正确负数。这个问题的根源在于“初始化的值代表了错误的最优假设”——把maxSum初始化为0等于默认“空子数组也是一种合法选择”但题目要求必须选一个非空子数组。解决办法有两个要么初始化maxSum为nums[0]循环从1开始要么初始化为INT_MIN。7.4 判断子序列的TLE问题392用DP做不会TLE但如果把DP定义搞成“以i结尾”并且每次内层循环从头开始复杂度会退化到O(n*m)且常数很大在极端情况下可能超时。我在训练营里看到有同学用三维DP去解决虽然能过但完全没必要。如果你只是做这一道题双指针是最优方案如果你为了系列题目练DP就用“只跳过t的字符”那版实现逻辑最清晰也不容易出错。7.5 二维DP滚动数组优化时的“覆盖顺序”问题这是我个人最想强调的一个坑。在做1143时很多人写完二维版本后想优化空间改成一行dp结果发现答案不对。原因在于当内层循环从左向右更新时dp[j-1]已经被当前行更新过了不再是上一行的dp[j-1]导致dp[i][j] dp[i-1][j-1] 1这一步计算错误。解决办法是内层循环从右向左遍历这样dp[j-1]还是上一行的值。这个“倒序更新”的技巧在很多一维DP压缩中都会用到比如背包问题。建议在训练营阶段就养成“压缩空间时先画表格搞清楚每个值的依赖方向”的习惯而不是死记倒序。8. 实操心法这套题单怎样刷收益最大最后分享一点我个人的刷题经验。这四道题如果只是“看题→看题解→写代码→AC”收获会非常有限。我建议按以下三步来刷第一步先自己尝试定义DP状态不管能不能写出正确的转移方程先写下来。哪怕错了也要能说清楚“我为什么这么定义”。这个过程是训练DP直觉的核心。第二步看题解时不要只看代码重点看“为什么这样定义状态”和“为什么这样转移”。尤其要关注递推公式中每一步的语义——比如dp[i][j] max(dp[i-1][j], dp[i][j-1])要能用自己的话解释“这是在做两个方向的放弃决策”。第三步AC之后做变式训练。1143做完可以接着做1035和392正好形成LCS的三连53做完可以试试“环形子数组的最大和”、“乘积最大子数组”体会状态定义如何随问题约束而变化。还有一个很多高手都在用的技巧每道题AC后把dp表格打印出来手推一遍小样例。比如text1abcde, text2ace手动填一遍表格你就能直观看到“相等分支”如何沿着对角线累加“不等分支”如何向左和向上取max。这个习惯在学习DP初期比狂刷十道题都有效。我在实际带训练营的过程中发现学员对DP的恐惧大多来自“状态定义太抽象”。但只要你能把每个状态对应到“输入的某一段前缀上”再把转移方程翻译成“当前字符匹配/不匹配时的两种选择”DP就从玄学变成了逻辑推导题。第四十九天的这四道题恰好就是训练这种翻译能力的最佳素材。