刷算法题刷到动态规划这个阶段很多人的感受是“递推公式一看就懂自己写就废”。尤其是连续几道题放在一起做题目之间长得很像但递推逻辑微妙地差那么一点写出来的代码就跑偏。这期训练营安排的第六十三、五十三天的六道题恰好就是这种“同族不同源”的典型组合300、674、718、1143、1035、53。把这六道题放在一起刷最大的价值不是多背几个公式而是真正理解dp数组下标的含义、遍历顺序和递推来源这三者之间是怎么联动的。这批题目本质上是同一类问题的不同变体都在求某个序列或两个序列的“最优子序列/子数组”。但“连续”和“不连续”在状态转移上的体现完全不同“单序列”和“双序列”在dp数组维度上的跃迁也很有讲究。所以这篇不按题目顺序逐题过而是按递推逻辑分组拆解先看单序列的两道300、674再看双序列的连续版本718再看不连续版本1143、1035最后用53收尾刚好把最大子序和作为整个动态规划“状态定义”思路的一次浓缩。1. 这批题目的真实关联维度与连续性两个变量在交叉变化很多人刷题喜欢一道一道孤立着刷其实非常亏。动态规划这部分的题目最值得训练的就是“在相似结构里识别差异”的能力。第六十二、六十三天的六道题正好构成一个完整的对比矩阵。先看题目之间的亲缘关系。300和674都是在单个数组上求递增子序列区别只有一个要不要连续718和1143都是在两个数组字符串上求匹配子序列区别也是连续还是不连续1035则是1143的一个几何包装本质上没有任何新算法53是在单数组上求连续子序和和674有某种对称性也直接关系着后续的“状态压缩”能走多深。这六道题的递推公式如果背的话半天就能背完。但考场上一换条件就懵根本原因是没有理解公式是怎么从“连续/不连续”这个约束里长出来的。连续意味着什么意味着状态只能从紧邻的上一个位置转移过来不能跳不连续意味着什么意味着状态可以从任意更早的位置转移过来所以通常需要另一层循环回头看。这两个约束直接决定了代码里是if (nums[i] nums[i-1])还是for (int j 0; j i; j)。另外维度也在变。单序列问题用一维dp数组就够但一旦涉及两个序列dp数组就要升到二维因为你要同时记录两个序列各自的推进位置。718、1143、1035这三道题全部是这个套路。而维度的提升带来一个直接后果空间复杂度从O(n)涨到O(n*m)。这也是后面做滚动数组优化的动机。下面不按题目序号走按递推结构走。先看最好理解的单序列连续版本674再回头看更经典也更“重”的300这样更容易建立“约束不同导致循环不同”的直觉。2. 单序列题组674是“看一眼前一个”300是“回头看前面所有”2.1 674最长连续递增序列递推来源被锁死在相邻元素674的题意很朴素找出数组里最长的连续严格递增段。比如[1,3,5,4,7]答案是[1,3,5]长度34,7虽然也递增但只连续了两项。状态定义比较直白dp[i]表示“以 nums[i] 结尾的最长连续递增序列长度”。这里有个关键习惯是训练营反复强调的dp[i] 说的是“以 i 结尾”不是“前 i 个元素里最优”。这两者在连续类问题里区别不大但在不连续类问题里会直接影响递推逻辑。养成习惯后面对300就不会踩坑。递推来源只有一条路既然要求连续递增那么dp[i]唯一能依赖的只有dp[i-1]。如果nums[i] nums[i-1]说明当前元素可以接在上一个元素后面长度加一否则只能另起炉灶从1重新开始。所以核心代码就三行vectorint dp(nums.size(), 1); for (int i 1; i nums.size(); i) { if (nums[i] nums[i-1]) { dp[i] dp[i-1] 1; } }注意这里没有else分支因为dp[i]初始化就是1不进if也默认自己是新序列的起点。这种“初始化兜底 条件触发转移”的写法在动态规划里非常常见可以少写很多分支判断。这道题的复杂度是O(n)因为每次只回头看前一个位置。它其实不需要动态规划用贪心双指针也能做但作为DP入门题价值不在于“最优解”而在于让你体会连续约束下递推来源为什么被压缩到i-1。我刷的时候犯过一个低级错误把nums[i] nums[i-1]写成nums[i] nums[i]这种笔误属于低级错误但还有一种隐蔽一点的错误是拿dp[i-1]去和nums[i]比较比如if (nums[i] nums[i - dp[i-1]])这种自作聪明的写法想跳着比较起点实际上一旦中间有断层就彻底错了。连续类问题不要试图跳老老实实比相邻。2.2 300最长递增子序列不连续所以必须往前扫300是很多人动态规划入门后“第一道真正卡住的题”。题意不需要连续只要保持相对顺序从数组中挑出若干个数组成递增序列求最大长度。经典例[10,9,2,5,3,7,101,18]答案是4[2,3,7,101]。状态定义依然是dp[i]表示“以 nums[i] 结尾的最长递增子序列长度”。但递推来源完全不同了。因为不要求连续当前元素可以接在任意一个位于它前面的、值比它小的元素后面。你必须枚举所有j i去看哪些nums[j] nums[i]然后从这些候选里选dp值最大的那个接上vectorint dp(nums.size(), 1); int result 1; for (int i 1; i nums.size(); i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } result max(result, dp[i]); }这道题有几点很值得说。第一这里dp[i]的更新是“对所有j取max”不是只有一个固定来源。所以定初始化为1非常关键哪怕前面找不到任何能接的位置dp[i]也至少有1自己单独成一个子序列。第二最终答案不是dp[n-1]而是整个dp数组的最大值。这个细节特别容易错。因为“以最后一个元素结尾”的最长递增子序列大概率不是全局最长。训练营里很多同学第300题的结果初始化为dp[0]结果数组长度为1时没问题长度一大就漏了。惯例是设result *max_element(dp.begin(), dp.end())或者边算边更新。第三复杂度是O(n²)。n小于等于2500时没问题但如果你在面试里遇到n到10⁵级别的数据这个写法会超时需要用贪心二分优化到O(n log n)。不过训练营这个阶段不太会深挖O(n²)的DP写法是基础必须先把递推逻辑吃透再考虑进阶。我在实际给其他学习者看代码的时候发现300和674放在一起对比最大的口感差异就在这里674是固定回头路300是漫无目的地全扫。全扫就带来一个隐含代价你在代码里多写了一层循环。这层循环就是“不连续性”四个字在代码层面的实体化。2.3 两道单序列题的共性总结先把这两道的对比沉淀成一句话连续意味着递推来源唯一不连续意味着递推来源需要枚举。这句话可以推广到几乎所有“子序列/子数组”类动态规划题目。674只用比nums[i-1]300要循环枚举所有nums[j]差的这一层循环就是约束严格程度的差异。做题时先问自己“要不要连续”比先默写模板重要得多。另外这两道题的状态定义都坚持“以 i 结尾”这是为了递推时能明确知道序列末端是什么值方便判断能否接上。如果你用“前 i 个元素中的最优”来定义dp那你就丢失了末端值无法判断接续条件。这是动态规划里一个非常核心的设计原则状态必须包含做出下一步判断所需的全部信息。3. 双序列题组第一站718的二维DP与“连续”的转移细节3.1 二维dp到底在记录什么718最长重复子数组题意是两个整数数组找出最长的相同且位置连续的子数组长度。比如nums1 [1,2,3,2,1]、nums2 [3,2,1,4,7]结果应该是3[3,2,1]。从单序列跨到双序列dp数组的维度从一维跳到二维。这个跳升经常让初学者懵为什么不能继续用一维dp做两个数组我的理解方式是这样的两个序列匹配时“当前走到哪里”由两个坐标共同决定你在nums1走到位置 i在nums2走到位置 j这个状态必须同时记录两个坐标否则无法判断下一步匹配。所以dp数组天然是二维的dp[i][j]表示“以 nums1[i] 结尾且以 nums2[j] 结尾的公共子数组的最大长度”。这里的“结尾”概念和单序列一脉相承。因为要求连续递推只能在两个数组同步往前走时发生。如果nums1[i] nums2[j]那说明这两个位置可以当作公共子数组的末端而它前面的部分是否连续相同就看dp[i-1][j-1]的值。于是if (nums1[i] nums2[j]) { dp[i][j] dp[i-1][j-1] 1; }注意这个递推公式里只有斜对角线的回退没有dp[i-1][j]或dp[i][j-1]的参与。原因就是“连续”公共子数组要么在[i-1][j-1]的基础上延长要么就从0重新开始。中间隔了一个不匹配的位置前面的长度就全部作废不能拼凑。3.2 下标从1开始避免边界判断的写法如果dp数组严格用0下标表示数组的实际首元素那么i0或j0时访问dp[i-1][j-1]就会越界代码里得加一堆if。更清爽的做法是把dp数组开成(m1) x (n1)让dp[i][j]表示“以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组长度”。这里空出来的第0行第0列是一个哨兵位天然是0代表“任何数组和空数组的最长公共子数组长度为0”。这样递推时不需要任何边界判断vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0)); int result 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; result max(result, dp[i][j]); } } }到这里可以停下来感受一下这段代码为什么比前面300看起来“干净”。因为它把边界问题用“加一行哨兵”消解掉了而不是到处写判断。这是动态规划以及很多二维DP问题的常用技巧在1143里同样适用。再提一个滚动数组的细节。718这类二维DP每一行的dp[i][j]只用到了上一行dp[i-1][j-1]的值所以理论上可以压缩成一维数组只保留上一行。但有个坑遍历j从右往左或从左往右会影响dp[j-1]读到的到底是当前行还是上一行。因为dp[i-1][j-1]在压缩后对应一维数组里的dp[j-1]如果你从左往右更新dp[j-1]已经在当前行被覆盖了读到的就是dp[i][j-1]而不是dp[i-1][j-1]结果直接错。因此必须让j从大到小遍历保证更新dp[j]时dp[j-1]还是上一行的旧值。vectorint dp(nums2.size() 1, 0); for (int i 1; i nums1.size(); i) { for (int j nums2.size(); j 1; j--) { if (nums1[i-1] nums2[j-1]) { dp[j] dp[j-1] 1; } else { dp[j] 0; // 连续断了必须清零 } } }这里还有个更隐蔽的坑压缩后必须加else dp[j] 0;。为什么因为二维版本里dp[i][j]默认是0不相等时它不会被上一行污染但一维滚动数组复用的是上一行的旧值如果你不在不匹配时清零旧的长长度会被错误地带到下一轮比较里。这个错误我见过很多次包括我自己第一次写滚动数组也没注意到。连续类问题的滚动数组清零几乎是必须的操作。这一点在下一批双序列题里反过来因为不连续版本在else分支要继承上方或左方的最大值不能清零。4. 双序列题组第二站1143和1035是“不连续”与“几何包装”4.1 1143递推为什么多了else分支1143最长公共子序列求两个字符串的最长公共子序列长度子序列不要求连续。比如text1 abcde、text2 ace答案是3ace。状态定义延续二维套路dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。但注意这里dp的含义其实是“前i个字符和前j个字符的最优结果”而不是“以某个位置结尾的结果”。为什么不沿用“以i结尾”因为不连续场景下公共子序列的末端位置不好锁定一个子序列的结尾可能不是当前比较的字符。所以这题的状态定义改成“前i个前j个”直接记录全局最优。递推分两种情况。第一种当前字符相等text1[i-1] text2[j-1]那这个字符可以接在两个前缀最后面显然dp[i][j] dp[i-1][j-1] 1。第二种当前字符不相等这时的处理方式和718形成鲜明反差不能直接放弃而是要从dp[i-1][j]和dp[i][j-1]里取最大值。为什么打个比方你手里有两串积木当前末尾两块对不上。这种情况下你仍然可能从“去掉text1末尾”或“去掉text2末尾”的结果中得到一个最长公共子序列。dp[i-1][j]是不看text1当前这个字符时已经得到的最优结果dp[i][j-1]是不看text2当前这个字符时已经得到的最优结果。这两个结果都可能是全局最优的候选所以要取max。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]); } } }真正理解和718的差异对视觉冲击力的对比非常有效718里如果不相等就什么都不做或者滚动数组版本里清零因为连续断了接不上1143里如果不相等反而要“缓冲”一下把前面的最优情况继承下来。这是“连续”与“不连续”在二维场景下最本质的分水岭。连续问题的dp是一个“必须建立在末尾匹配”的局部状态不连续问题的dp是一个“扫描到哪里就累积到哪”的全局状态。说到这个else分支还有一个常见疑问既然不相等时取的是max(dp[i-1][j], dp[i][j-1])那为什么不加上dp[i-1][j-1]答案是dp[i-1][j-1]已经被包在前两者里面了。dp[i-1][j]是从dp[i-1][j-1]再往j方向推进得到的只会更大不会更小。所以max两个就够了写三个也不会错纯属冗余。4.2 1035不相交的线把几何约束翻译成序列约束1035题意可以抽象为在两条平行排列的数字序列之间用直线连接相等的数字要求线不能相交求最多能画多少条不交叉的线。题目的表述看起来像几何题实际上就是1143的换皮。为什么说它等价于最长公共子序列你要连的线是nums1[i] nums2[j]的匹配对。如果线不相交意味着你按顺序扫描两条序列连接顺序必然是“同步前进”的——前一条线连完之后后一条线的两个位置都必须往后走。这正好和子序列的定义吻合保持相对顺序不变地挑选若干数字。只要挑出来的配对在两条序列里都保持相同的前后顺序画线就不会交叉。反过来如果连线相交说明其中一条序列里先出现的数在另一条序列里对应的位置却靠后这就是相对顺序被破坏等价于子序列顺序错乱。所以1035的解法就是完完全全的1143代码一行都不用改。我记得刚发现这个等价关系的时候相当震撼。训练营的题单里把这两道放一起目的就是让你看到“换包装不换算法”的题目识别能力有多重要。面试里很多题说得天花乱坠抽象到序列层面就是LCS。用1143的代码直接跑1035的用例结果完全正确。这个过程实质上是一个建模练习遇到几何约束先想能不能用序列关系表达。不能相交这个约束翻译过来就是“匹配顺序不能回退”这比去模拟画线再检测交点高效得多。4.3 双序列题组的小结718和1143放在一起看二维DP的形态一下子立体了起来。连续版本像是一个个“锁链”断一环前面全断不连续版本像是一个“叠加态”每一步都在合并前面所有可能性里的最大值。所以代码上差一个else思想上差一个维度连续问题你要盯住“以xxx结尾”的局部状态不连续问题你要放宽成“前xxx个的整体最优”。这种状态定义视角的切换是这批题目最重要的训练点。滚动数组方面不连续版本也可以压缩。1143的一维压缩比718稍复杂一点因为dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个值压缩后相当于依赖dp[j-1]上一行斜对角、dp[j]上一行正上方、dp[j-1]当前行左侧。这里dp[j-1]被同时用作上一行斜对角和当前行左侧直接压缩会互相覆盖。处理办法是先把dp[j-1]暂存到上一个变量里再用它更新。这种细节在纯二维的写法里不需要考虑但真到了大数组场景空间从O(n*m)压到O(m)是实打实的优化建议有时间还是掌握一下。5. 53最大子序和从“序列最优”回归“元素结尾”5.1 这道题为什么放在这批DP的最后53最大子序和求数组中具有最大和的连续子数组返回其最大和。经典例[-2,1,-3,4,-1,2,1,-5,4]答案是6[4,-1,2,1]。题目本身很简单甚至有人觉得不需要动态规划贪心也能做。但放在这批题末尾它的价值是帮你做一次思维收拢你刚看完了二维DP、LCS、LIS突然来一道“单序列连续和最大”的题需要用最朴素的“以 i 结尾”状态重新建立递推。状态定义dp[i]表示“以 nums[i] 结尾的最大连续子数组和”。这里有个直觉分配问题很多人会把它定义成“前 i 个元素的最大子序和”这样定义也能求但递推时没法确定子数组从哪里开始状态里缺“以谁结尾”的信息。递推逻辑核心是一个判断题是把 nums[i] 接在前面的子数组后面还是从 nums[i] 重新开一个新子数组判断标准很简单比较哪个更大vectorint dp(nums.size(), 0); 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]); }如果dp[i-1]是负数那接上去只会让当前和更小不如从nums[i]重新开始。这个max的写法本质是在“延续旧序列”和“开启新序列”之间做贪心选择。和300的枚举不同这里的选择只有两个候选因为连续约束决定了新序列不能跳过任何元素只能要么接上要么另起。5.2 从O(n)到O(1)为什么这道题能压到头53这题之所以能空间压缩到常数级别是因为递推只依赖dp[i-1]跟i-2、i-3全部无关。用一个变量滚动即可int cur nums[0], result nums[0]; for (int i 1; i nums.size(); i) { cur max(cur nums[i], nums[i]); result max(result, cur); }这和674的dp[i-1] 1是一个模式的。连续类问题天然依赖更少的历史状态空间压缩空间大不连续类问题要往前看所有历史压缩只能靠“滚动数组”这种把二维压成一维的手段无法压到O(1)。这是题目约束对算法复杂度影响的一个非常直观的例子。顺便说一下贪心解法很多人知道贪心也能解53但往往会困惑它与DP的区别。贪心的写法是sum max(sum nums[i], nums[i])然后维护maxSum。其实这跟上面滚动数组的DP写法从数值上完全一致——当dp[i-1]为负时选择重新开始这就是贪心策略。所以从这个角度说DP和贪心在53上是同一枚硬币的两面。区别只是DP写法强调状态定义和转移的推导贪心写法强调局部最优决策。两种都要会写笔试里有的公司只要求答案有的会在面试里追问原理用DP作答更符合“算法思维”的定义。5.3 最后补一个负例易错点最大子序和的经典陷阱是数组全为负数。比如[-3,-1,-4,-2]正确答案是 -1也就是最大的那个负数。很多初学者的直觉是“负数都会拉低和所以答案应该是0”然后初始化result 0结果整个数组为负时直接错。所以dp[0]和result都必须初始化为nums[0]不能是0。负数场景是把“最大”这两个字抠明白的好题目最大并不等于大于0。6. 这批题刷完动态规划最值钱的三个习惯是什么最后想聊的其实是方法论层面的收获。这批题刷完我觉得真正值钱的不是学会了六道题本身而是反复训练出来的三个习惯。第一个习惯写递推公式之前先问“连续还是不连续”。连续就把状态锁死在“以xxx结尾”递推来源只能看相邻位置不连续就打开历史窗口要么枚举全部要么在二维DP里通过max合并左右来源。这两个分支在代码上相差不大但思路决定了你能不能往对的方向走。第二个习惯dp数组的语义决定一切。同样一道题把dp[i]理解成“以i结尾”还是“前i个最优”推导出来的递推公式可以完全不同。300如果理解成“前i个元素里的LIS长度”递推就没法做因为你不知道当前子序列的结尾值是多少也就没法判断能否延长。状态缺失关键信息递推就必须停下来。状态定义要“留得住必要信息控得住维度规模”这是动态规划设计最需要练习的一点。第三个习惯边界初始化永远是一个独立检查步骤。dp[0]是多少、result初始是多少、dp数组要不要多开一行哨兵、滚动数组要不要清零这些单独拿出来写比混在递推里调试要省事得多。我刷这批题时每一次“答案不对”最后定位到的几乎都是初始化问题而非递推公式本身写错。所以现在设计题解时习惯先单独写一行注释“初始化”再写“递推”把两者用注释分开自测时会非常清晰。六道题相互之间的对比关系有点像一张小型的算法知识图谱值得自己动手画一遍。不过画完之后真正带走的还是上面的三个习惯。动态规划的题目刷到后期你会发现题目的壳一直在换状态定义和转移方向的内核始终是那几个经典模型。把这道题组的关联结构吃透后面再遇到“编辑距离”“通配符匹配”这些更复杂的题至少不会被二维dp和连续约束这两道坎绊住。