动态规划这块最大子段和和最长公共子序列基本是绕不开的两道坎。前者是一维线性DP的入门样板后者是二维序列DP的教科书样本几乎所有讲到动态规划DP的课程都会把它们拎出来单独说一遍。我这些年刷题、带人、写题解发现一个规律能把这两道题从头到尾讲清楚的人后面学区间DP、树形DP、状态压缩都会顺很多反过来这两道题里含糊过去的坑会在后面反复以各种形态冒出来。这篇就按我自己的理解路径把这两道题从为什么这么定义状态到代码怎么写、怎么调、怎么优化完整拆一遍中间会穿插我实测过的多种写法和踩过的坑。适合刚学完递归和基础枚举、准备进入DP的读者也适合写了很久但一直靠背模板过题、想重新把底层逻辑理顺的读者。1. 先想清楚这两个问题为什么值得单独拎出来讲1.1 状态定义的颗粒度直接决定你后面写多少行代码很多人学DP卡住的地方不是不会写循环而是不知道该把状态定义成什么。最大子段和和最长公共子序列恰好是两种典型的颗粒度示范。最大子段和的状态是以第 i 个元素结尾的最大子段和注意这个以 i 结尾四个字极其关键。如果定义成前 i 个元素里的最大子段和转移方程就写不出来因为你不知道新加进来的元素能不能接上前面那段。加上以 i 结尾这个限定最后一个元素就被钉死了剩下的选择只有两个接上前面的段或者自己另起一段。这就是典型的用限制换转移可行性。最长公共子序列的状态是a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度。注意这里用的是前 i 个因为两个字串之间没有最后一个必须匹配这种强制约束长度本身就是我们要的答案所以可以直接用前缀。这两种颗粒度没有优劣取决于题目问的是什么。翻译成一句可以复用的经验如果答案是最优值而不是某个位置的局部最优值通常可以用前缀状态如果转移需要依赖上一个被选中的元素是谁就得把位置信息塞进状态里。1.2 两个模型其实是同一套骨架的两种变体把这两道题的代码摆在一起看你会发现骨架惊人地一致定义状态、写转移、定初值、定遍历顺序、定答案位置。区别只在于最大子段和的转移是线性的一前一后LCS 的转移是二维的左、上、左上。我用一张表把这两道题的骨架并排放一下方便对照对比项最大子段和最长公共子序列状态维度一维 dp[i]二维 dp[i][j]状态含义以 i 结尾的最大和前 i 个与前 j 个的LCS长度决策来源接上 / 另起匹配 / 取左 / 取上遍历顺序i 从 0 到 n-1i 外层、j 内层均正序答案位置全局 max不是 dp[n-1]dp[n][m]空间优化一个变量一行数组 一个变量这张表里最容易被忽略的是答案位置那一行。最大子段和的答案不在 dp[n-1]而在所有 dp[i] 里的最大值这个点后面会专门展开讲因为它是新手最容易错的地方之一。1.3 动手写之前先确认三件事在敲代码之前我现在的习惯是先在纸上确认三件事确认完再动手能省掉大量调试时间。第一件事是边界语义。最大子段和里子段到底允不允许为空如果允许空全负数数组的答案是 0如果不允许空答案是最大的那个负数。这两种定义在题目里都出现过读题时必须抠清楚。LCS 里空串算不算公共子序列算所以 dp[0][j] 和 dp[i][0] 全部为 0这个基本没有歧义。第二件事是下标体系。是 0-based 还是 1-based我强烈建议 DP 表的行列下标从 1 开始把第 0 行和第 0 列留给空串或空段代码里写 dp[i-1][j-1] 的时候不容易搞混。代价是访问原数组要写 a[i-1]但这笔账很划算。第三件事是数据规模。最大子段和如果是 n ≤ 2×10^5那只能 O(n) 或 O(n log n)LCS 如果 n、m 都在 10^3 量级O(nm) 完全够但如果题目给的是两个排列、n 到 10^5那 O(nm) 必爆得换思路。规模决定算法选型这一步偷懒后面重写的时间成本更高。注意别一上来就套记忆里的模板。先花两分钟确认这三件事比写完发现题意理解错了再推倒重来要快得多。2. 最大子段和从三层循环到一次遍历的瘦身过程2.1 先把题目边界抠干净非空还是可空最大子段和的标准表述是给一个整数序列找出一个连续的子段使它的和最大。这里连续是硬约束子段至少包含一个元素是常见约定也就是非空。非空带来的最直接后果是如果数组全是负数答案是其中最大的那个负数而不是 0。这个结论看起来很朴素但实际写代码时特别容易翻车因为很多人脑子里默认不选就是 0。还有一种变体是允许空段这时候全负数数组答案就是 0。判断方法很简单看题目描述里有没有可以为空或至少包含一个数。如果没有明确说默认非空。我踩过一次典型的坑某道题我按允许空段的思路写了ans max(0, ...)结果全负数测试点直接错。后来养成习惯函数命名上直接把语义写出来比如max_subarray_nonempty这样调用的时候不会记混。2.2 状态定义是怎么一步步想出来的先用最笨的办法想枚举左端点 l 和右端点 r把中间加起来。这是 O(n^3)n 到 100 就跑不动了。第一步优化预处理好前缀和区间和变成 O(1)整体降到 O(n^2)。n 到 5000 勉强能过再大就不行了。想再降就得换个角度不要枚举区间而是从左往右扫过去边扫边维护一些信息。扫到第 i 个元素时考虑所有以 i 结尾的子段。这些子段分成两类只有 a[i] 一个元素的和以 i-1 结尾的某个子段再接上 a[i]。要让第二类和最大显然应该挑以 i-1 结尾的最大子段和来接。于是状态就定出来了dp[i] 以 a[i] 结尾的最大子段和转移方程随之而来dp[i] max(a[i], dp[i-1] a[i])初值是dp[0] a[0]。最终答案是max(dp[0..n-1])因为最大子段可能以任何一个位置结尾不是必须以最后一个元素结尾。这个推导过程里有一个隐含前提如果 dp[i-1] 是负数那么接上它只会拖后腿不如另起一段。这一步就是整个算法的灵魂也是很多人知道代码但讲不出为什么的地方。2.3 三版代码对照与实测我把三个版本都写出来你可以直接跑感受一下差距。第一版纯暴力枚举加求和def max_subarray_brute(a): n len(a) best a[0] for i in range(n): for j in range(i, n): s sum(a[i:j1]) # 每次重新求和浪费 best max(best, s) return best这段代码在 n 200 时大约要跑几十万次加法n 到 1000 就明显卡了。第二版前缀和优化def max_subarray_prefix(a): n len(a) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] a[i] best a[0] for i in range(n): for j in range(i 1, n 1): best max(best, pre[j] - pre[i]) return best这里语义上更接近枚举左端点 i再枚举右端点 j只是区间和用前缀和查表。复杂度 O(n^2)。第三版Kadane 算法也就是标准解def max_subarray(a): cur best a[0] for x in a[1:]: cur max(cur x, x) # 接上还是另起 best max(best, cur) return best这里cur就是滚动后的 dp[i]best就是全局答案。整个循环只做两次比较和一次加法n 10^6 也就几十毫秒的事。我第一次从 O(n^2) 改成 O(n) 的时候心里是有怀疑的这么简单的循环真的对吗后来自己手动跑了几组数据包括全负数、单元素、交替正负这些情况才彻底服气。手动模拟一遍的过程强烈建议你也做一次尤其是记录每一步的 cur 和 best 变化比看十遍题解管用。2.4 滚动变量的空间压缩dp 数组其实完全不需要。观察转移方程dp[i] 只依赖 dp[i-1]前面所有值都用不上了。所以用一个变量cur滚动就行空间从 O(n) 降到 O(1)。这里有个细节值得说虽然我们只保留了最新的 dp 值但答案不能跟着滚动掉因为最大子段不一定以最后一个元素结尾。所以必须单独用一个best变量实时更新。很多人压缩空间的时候顺手把 best 也搞没了最后返回 cur那就错了。如果题目还要求输出这个子段本身起点和终点下标那就不能只滚一个值了得一边更新一边记录起点。常见的做法是当cur x x时说明另起一段此时把起点更新为 i每当 best 被刷新就把当前起点和 i 存进结果变量。def max_subarray_with_index(a): cur best a[0] start cur_start 0 end 0 for i in range(1, len(a)): if cur a[i] a[i]: cur a[i] cur_start i else: cur a[i] if cur best: best cur start, end cur_start, i return best, start, end这段代码我在面试里被问到过两次考的就是空间压缩的同时还能不能还原方案。2.5 环形与二维扩展同一套思想换皮把数组首尾接起来变成环问最大子段和这是很经典的一道变体。思路分两种情况。第一种答案子段没有跨越首尾那就是普通的线性最大子段和。第二种答案子段跨越了首尾那么它相当于整个数组的和减去中间那段连续的最小子段和。因为跨越首尾的部分 总和 - 中间挖掉的部分要让结果最大就要让挖掉的部分最小。代码大概是这样def max_subarray_circular(a): total sum(a) best max_subarray(a) # 非空最大子段和 if best 0: return best # 全负数环形也只能取单个元素 cur_min mn a[0] for x in a[1:]: cur_min min(cur_min x, x) mn min(mn, cur_min) return max(best, total - mn)那个if best 0的判断就是前面说的非空带来的坑。如果全是负数total - mn 会等于 0对应什么都不取但题目要求非空所以必须特判掉。再往二维推就是最大子矩阵和。做法是枚举行的上下边界 top 和 bottom把这一段的每一列求和压成一个一维数组然后跑一次 Kadane。复杂度 O(n^2 * m)n、m 都在几百的时候可以接受。def max_submatrix(mat): n, m len(mat), len(mat[0]) best -10**18 for top in range(n): col [0] * m for bottom in range(top, n): for k in range(m): col[k] mat[bottom][k] best max(best, max_subarray(col)) return best这里的核心思想是降维把二维问题在某一维上枚举掉剩下的维度压成一维。这个套路后面在状态压缩DP里还会反复出现。3. 最长公共子序列二维DP的经典样本3.1 子序列和子串一字之差天壤之别先把概念钉死。子序列是从原串里删掉若干字符可以一个都不删后剩下的、保持原有相对顺序的序列不要求连续。子串是必须连续的一段。举例子abcde 和 ace 的公共子序列但 ace 不是 abcde 的子串。abcde 和 bc 的关系里bc 两者都算。这个区别直接决定状态转移。求最长公共子序列时字符 a[i-1] 和 b[j-1] 不相等我们还能跳过其中一个继续往前比求最长公共子串时一旦不相等当前这一段就断了必须清零重来。很多新手写 LCS 时把else分支写成dp[i][j] 0那就变成求最长公共子串了题目要求一变答案直接差一大截。这个错误我在帮人看代码时见过不下十次。3.2 dp[i][j] 的语义与转移推导状态定义dp[i][j]表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子序列长度。推导按 a[i-1] 和 b[j-1] 是否相等分两路。如果相等这两个字符可以直接配成一对放在公共子序列的末尾那么长度就是dp[i-1][j-1] 1。这里有个常见疑问凭什么相等就一定配上会不会不配上反而更长答案是不会因为配上之后新增的这个字符在最末尾不影响前面的任何选择属于白赚一个。如果不相等那么 a[i-1] 和 b[j-1] 至少有一个不在最终的公共子序列里。于是考虑三种情况a[i-1] 不参与答案取 dp[i-1][j]b[j-1] 不参与答案取 dp[i][j-1]两个都不参与答案取 dp[i-1][j-1]。第三种情况被前两种包含因为 dp 值单调不减所以只需要取前两个的最大值。转移方程dp[i][j] dp[i-1][j-1] 1 若 a[i-1] b[j-1] dp[i][j] max(dp[i-1][j], dp[i][j-1]) 否则初值dp[0][j] dp[i][0] 0对应空串和任何串的公共子序列长度都是 0。答案是dp[n][m]。注意这里和最大子段和不同LCS 的答案就在右下角因为我们要的本来就是两个完整串的结果。3.3 代码实现与路径回溯基础版def lcs_length(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[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[n][m] 往回走。规则是如果 a[i-1] b[j-1]这个字符属于答案记录它然后 i 和 j 同时减一否则比较 dp[i-1][j] 和 dp[i][j-1]往大的那边走。def lcs_path(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) res [] i, j n, m while i 0 and j 0: if a[i-1] b[j-1]: res.append(a[i-1]) i - 1 j - 1 elif dp[i-1][j] dp[i][j-1]: i - 1 else: j - 1 return dp[n][m], .join(reversed(res))回溯时那个和的取舍会决定当两条路径长度相同时走哪条。两种都能得到合法答案但如果不小心写成并配错方向就可能出现死循环或者长度对不上。我个人的习惯是统一往上优先即dp[i-1][j] dp[i][j-1]时让 i 减一这样得到的解更稳定方便对拍。3.4 滚动数组优化的正确姿势二维 dp 表在 n、m 都到 5000 的时候就是 2500 万个格子即使存 short 也要几十 MB很多题的内存限制扛不住。优化思路是用两行滚动更进一步压成一行加一个变量。观察转移dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。这三个分别对应左上、上、左。用一行数组row在更新 row[j] 之前row[j] 存的是上一行的 dp[i-1][j]上row[j-1] 已经被更新成 dp[i][j-1]左而左上那个值会被 row[j] 覆盖掉所以必须用临时变量提前存起来。def lcs_rolling(a, b): n, m len(a), len(b) row [0] * (m 1) for i in range(1, n 1): prev 0 # 相当于 dp[i-1][0] for j in range(1, m 1): tmp row[j] # 保存 dp[i-1][j] if a[i-1] b[j-1]: row[j] prev 1 else: row[j] max(row[j], row[j-1]) prev tmp # 给下一列当左上 return row[m]这段代码我第一次写的时候错了两次。第一次忘了更新 prev第二次把 prev 的赋值放在了 if 之前导致匹配分支拿到的不是 dp[i-1][j-1]。后来我养成了一个习惯在代码旁边手写一遍三个角色的对应关系上 row[j] 旧值左 row[j-1] 新值左上 prev对照着敲基本一次就对。注意滚动数组省了空间但丢掉了完整的 dp 表也就没法回溯路径了。如果题目要求输出具体方案要么保留完整表要么另用别的方式记录决策。3.5 相邻变体最长公共子串与编辑距离最长公共子串的转移稍有不同相等时dp[i][j] dp[i-1][j-1] 1不相等时直接归零。答案是所有 dp[i][j] 里的最大值而不是右下角。这一点和最大子段和一样属于答案在全局的类型。def longest_common_substring(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] best 0 for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 best max(best, dp[i][j]) return best编辑距离又是同一族里的另一个成员转移是三种操作的取最小值def edit_distance(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] i for j in range(m 1): dp[0][j] j for i in range(1, n 1): for j in range(1, m 1): cost 0 if a[i-1] b[j-1] else 1 dp[i][j] min( dp[i-1][j-1] cost, # 替换 dp[i-1][j] 1, # 删除 dp[i][j-1] 1 # 插入 ) return dp[n][m]把这三个放在一起看你会发现二维序列DP的基本套路就是在 (i-1, j)、(i, j-1)、(i-1, j-1) 这三个格子里做文章具体怎么组合取决于题目允许什么操作、问的是什么。4. 完整落地两道题的实测与调试记录4.1 最大子段和整套代码与用例我平时写这类函数会顺手带一段自测把边界情况全覆盖上。def max_subarray(a): cur best a[0] for x in a[1:]: cur max(cur x, x) best max(best, cur) return best if __name__ __main__: cases [ ([1, -2, 3, 10, -4, 7, 2, -5], 18), ([-2, -1, -3], -1), ([5], 5), ([0, -1, 2, -3, 4], 4), ([-1, 0, -2], 0), ] for arr, expect in cases: got max_subarray(arr) print(arr, got, got, expect, expect, OK if got expect else FAIL)第二组[-2, -1, -3]就是专门用来打非空这个点的答案是 -1 而不是 0。第五组[-1, 0, -2]是混合了 0 的情况答案是 0因为单独取那个 0 就是合法子段。这几组数据看着简单但它们覆盖了全正、全负、含零、单元素、正负交替。我建议任何人写完这个函数都拿这几组跑一遍比随手造数据靠谱。4.2 LCS整套代码与用例def lcs_path(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) res [] i, j n, m while i 0 and j 0: if a[i-1] b[j-1]: res.append(a[i-1]); i - 1; j - 1 elif dp[i-1][j] dp[i][j-1]: i - 1 else: j - 1 return dp[n][m], .join(reversed(res)) if __name__ __main__: tests [ (abcde, ace, 3), (abc, abc, 3), (abc, def, 0), (, abc, 0), (bl, yby, 2), ] for a, b, exp in tests: ln, path lcs_path(a, b) ok OK if ln exp else FAIL print(f{a!r} vs {b!r} - len{ln} path{path!r} {ok})(bl, yby)这组比较有意思两个串没有相同字符答案 0回溯时应该一个字符都不输出。空串那组用来验证初值处理如果 dp 表开成 n×m 而不是 (n1)×(m1)这里会直接抛下标越界。4.3 大输入规模下的适配从 O(nm) 到 O(n log n)前面说了LCS 的 O(nm) 在 n、m 到 10^3 甚至 10^4 的时候都没问题但题目一旦给到 10^5就必须换思路。最典型的是在线评测平台上那道经典的 P1439 模板题给两个 1 到 n 的排列求最长公共子序列。关键突破口在于两个串都是排列元素互不相同。那么我们可以把第一个排列中的每个值映射成它的位置下标然后拿第二个排列去查这些下标得到一个下标序列。求这两个排列的 LCS等价于求这个下标序列的最长上升子序列。为什么等价因为公共子序列要求两个串里都出现且在两个串中的相对顺序一致。第一个串里的顺序就是下标自然序所以第二个串里的元素要按照在第一个串中出现的先后排列也就是下标严格上升。于是问题转成了 LIS。LIS 有 O(n log n) 的解法用二分维护一个最小尾部数组import bisect def lcs_permutation(a, b): n len(a) pos [0] * (n 1) for idx, v in enumerate(a): pos[v] idx seq [pos[v] for v in b] tails [] for x in seq: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)这里的tails[k]表示长度为 k1 的上升子序列中最小的末尾元素。这个数组本身是严格递增的所以可以二分。这道题的转换思路我印象特别深因为它示范了一件事很多看起来必须 O(nm) 的问题换个等价描述就能降一个量级。4.4 小数据对拍省时间的验证方式写完 O(n) 的 Kadane 或者滚动的 LCS 之后我心里的第一反应不是应该对了而是找个可信版本对拍一下。做法是写一个明显正确但很慢的版本比如 O(n^3) 的暴力随机生成几百组小数据两个版本跑同样的输入比对结果。import random def check_max_subarray(rounds500): for _ in range(rounds): n random.randint(1, 8) arr [random.randint(-10, 10) for _ in range(n)] fast max_subarray(arr) slow max(arr[i:j1] and sum(arr[i:j1]) for i in range(n) for j in range(i, n)) # 上面这行写法不严谨实际用嵌套循环更清楚 if fast ! slow: print(mismatch, arr, fast, slow) return print(all passed)对拍这个习惯值多少钱我自己算过它能挡掉我至少一半的低级错误尤其是边界和下标类的问题。写对拍只要五分钟找 bug 可能要半小时账很好算。5. 常见问题与排查技巧实录5.1 三类高频翻车现场第一类是状态定义和答案位置不匹配。最大子段和的 dp 定义在以 i 结尾答案就必须扫一遍所有 dp 取最大最长公共子串同理。如果你直接返回 dp[n] 或者 dp[n][m]在答案不以末尾结尾的题上必错。判断方法很简单问自己一句最优解一定在最后一个位置吗不是的话就必须全局取max。第二类是边界语义没对齐。全负数数组返回 0 还是返回最大负数取决于题目允许不允许空。这个错误特别隐蔽因为大部分测试数据都是正负混合恰好能过只有专门的全负数测试点会挂。我现在的习惯是写完先在脑子里过一遍全负数、全正数、含零、单元素、两个空串这五组。第三类是空间优化时把依赖关系搞乱。滚动数组里dp[i-1][j-1] 这个左上的值是最容易被覆盖的必须用临时变量提前存。LCS 滚动那版我第一次就栽在这上面。排查方法是把行和列的语义写在注释里逐个对照row[j]旧值、row[j-1]新值、prev分别代表哪个格。5.2 问题速查表现象大概率原因处理方式答案总是比预期小状态定义是以 i 结尾忘了全局取 max循环里持续更新 best全负数数组返回 0允许空段和非空段语义混淆明确题目要求非空时不与 0 取 maxLCS 长度明显偏小else 分支写成了清零退化成求子串改回取 max(dp[i-1][j], dp[i][j-1])结果对但不稳定回溯时相等路径的选择不一致固定优先级比如统一优先往上走内存超限二维表全开改滚动数组或存 short大数据超时O(nm) 扛不住 10^5排列场景转 LIS用 O(n log n)下标越界dp 表开成 n×m统一开 (n1)×(m1)0 行 0 列做哨兵环形题输出 0全负数时 total - min 得到空集特判 best 0 直接返回 best这张表里的每一条我要么自己踩过要么在别人的代码里见过不是凭空列的。5.3 我个人踩过的几个坑第一个坑是想当然的空间压缩。有段时间我看 LCS 的二维表不顺眼动手改成滚动数组结果写完直接错了。后来复盘发现我改的时候脑子里想的是只需要上一行但忘了 dp[i][j-1] 是本行新算出来的值这个依赖是左边。二维 DP 的滚动永远是上一行 当前行已经算出来的部分这一点想清楚了再动手能少很多返工。第二个坑是用 0 当作不可达标记。最大子矩阵和那道题里如果初始 best 设成 0遇到全负矩阵就会输出 0而正确答案是最小的那个负数。那之后我一律用-10**18这种明确不可达的值做初值虽然丑一点但不骗自己。第三个坑是对拍数据分布太单一。早期我造对拍数据都用random.randint(-10, 10)结果全是正负混合全负数的情况几乎撞不上。后来改成有意识地混入全负、全零、单元素这些边界才真正起到防护作用。数据造得随机不代表覆盖得全面。6. 这两个模型还能往哪延展6.1 最大子段和的线段树版本如果题目要求支持单点修改再查询区间最大子段和Kadane 就不够用了得请线段树出场。每个节点维护四个值区间和sum、最大前缀和pre、最大后缀和suf、区间最大子段和best。合并两个子节点时sum l.sum r.sum pre max(l.pre, l.sum r.pre) suf max(r.suf, r.sum l.suf) best max(l.best, r.best, l.suf r.pre)这四个式子背后的逻辑都很直白。比如pre要么完全落在左区间里要么覆盖整个左区间再延伸到右区间两种情况取大。best则要么在左边、要么在右边、要么跨中间左后缀 右前缀。单点修改和区间查询都是 O(log n)整体 O(n log n) 建树加 O(log n) 每次操作。我在做一道带修改的区间最大子段和题时一开始想用分块糊过去结果写了两百多行还过不了换成线段树之后代码短了一半效率还高。这个结构值得专门花时间掌握。6.2 和背包问题在思维上的互通有人觉得序列DP和背包DP是两套东西其实底层思维方式是一致的都是在某个位置做决策决策影响后续状态。背包问题的 dp[i][j] 表示前 i 个物品、容量 j 下的最大价值转移是选或不选LCS 的 dp[i][j] 表示前 i 个和前 j 个字符下的最长公共子序列转移是匹配或不匹配。共同点在于状态里包含了处理到哪了这个进度信息转移就是在当前位置做一次选择。背包的一维滚动和 LCS 的滚动数组本质也是同一件事——把只依赖上一层的维度压掉。学完这两个模型再去写 01 背包很多人会发现原来那些倒序枚举容量的技巧和 LCS 里保存左上值的技巧是同源的。顺带提一句动态规划在工程侧的应用也很广比如资源调度、路径规划、库存分配这类问题本质上都是分阶段决策 状态转移的模型只是状态空间比刷题时大得多工程上通常还要配合状态压缩和剪枝。6.3 后续练习路线如果这两道题你已经能独立写出来包括边界、滚动优化、路径回溯那接下来可以按这个顺序往下走先做最长上升子序列把 O(n^2) 和 O(n log n) 两版都写一遍顺便把二分的过程吃透。然后做编辑距离和最长公共子串感受同一套二维骨架的变体。再往上就是区间DP从石子合并、最长回文子序列这类题入手体会区间状态怎么定义。最后是树形DP和状态压缩把状态这个概念从数组下标扩展到集合和树节点上。每一步都别跳过对拍和边界测试。我见过太多人一路刷题一路背模板遇到变形题就懵。真正把状态定义、转移依据、空间时间优化这三件事想明白后面无论遇到什么新题型你都有办法自己推出来。最后分享一个我用了很久的小技巧每道DP题做完之后用一句话把状态定义写下来贴在代码注释第一行。比如dp[i] 表示以 i 结尾的最大子段和。这句话写不出来说明状态没想清楚写出来了但代码跟它对不上说明转移写错了。这个习惯帮我在复盘时省了大量时间也让我后来给别人讲题时能张口就说清楚每一个下标在干什么。
动态规划核心：最大子段和与最长公共子序列状态转移详解
动态规划这块最大子段和和最长公共子序列基本是绕不开的两道坎。前者是一维线性DP的入门样板后者是二维序列DP的教科书样本几乎所有讲到动态规划DP的课程都会把它们拎出来单独说一遍。我这些年刷题、带人、写题解发现一个规律能把这两道题从头到尾讲清楚的人后面学区间DP、树形DP、状态压缩都会顺很多反过来这两道题里含糊过去的坑会在后面反复以各种形态冒出来。这篇就按我自己的理解路径把这两道题从为什么这么定义状态到代码怎么写、怎么调、怎么优化完整拆一遍中间会穿插我实测过的多种写法和踩过的坑。适合刚学完递归和基础枚举、准备进入DP的读者也适合写了很久但一直靠背模板过题、想重新把底层逻辑理顺的读者。1. 先想清楚这两个问题为什么值得单独拎出来讲1.1 状态定义的颗粒度直接决定你后面写多少行代码很多人学DP卡住的地方不是不会写循环而是不知道该把状态定义成什么。最大子段和和最长公共子序列恰好是两种典型的颗粒度示范。最大子段和的状态是以第 i 个元素结尾的最大子段和注意这个以 i 结尾四个字极其关键。如果定义成前 i 个元素里的最大子段和转移方程就写不出来因为你不知道新加进来的元素能不能接上前面那段。加上以 i 结尾这个限定最后一个元素就被钉死了剩下的选择只有两个接上前面的段或者自己另起一段。这就是典型的用限制换转移可行性。最长公共子序列的状态是a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度。注意这里用的是前 i 个因为两个字串之间没有最后一个必须匹配这种强制约束长度本身就是我们要的答案所以可以直接用前缀。这两种颗粒度没有优劣取决于题目问的是什么。翻译成一句可以复用的经验如果答案是最优值而不是某个位置的局部最优值通常可以用前缀状态如果转移需要依赖上一个被选中的元素是谁就得把位置信息塞进状态里。1.2 两个模型其实是同一套骨架的两种变体把这两道题的代码摆在一起看你会发现骨架惊人地一致定义状态、写转移、定初值、定遍历顺序、定答案位置。区别只在于最大子段和的转移是线性的一前一后LCS 的转移是二维的左、上、左上。我用一张表把这两道题的骨架并排放一下方便对照对比项最大子段和最长公共子序列状态维度一维 dp[i]二维 dp[i][j]状态含义以 i 结尾的最大和前 i 个与前 j 个的LCS长度决策来源接上 / 另起匹配 / 取左 / 取上遍历顺序i 从 0 到 n-1i 外层、j 内层均正序答案位置全局 max不是 dp[n-1]dp[n][m]空间优化一个变量一行数组 一个变量这张表里最容易被忽略的是答案位置那一行。最大子段和的答案不在 dp[n-1]而在所有 dp[i] 里的最大值这个点后面会专门展开讲因为它是新手最容易错的地方之一。1.3 动手写之前先确认三件事在敲代码之前我现在的习惯是先在纸上确认三件事确认完再动手能省掉大量调试时间。第一件事是边界语义。最大子段和里子段到底允不允许为空如果允许空全负数数组的答案是 0如果不允许空答案是最大的那个负数。这两种定义在题目里都出现过读题时必须抠清楚。LCS 里空串算不算公共子序列算所以 dp[0][j] 和 dp[i][0] 全部为 0这个基本没有歧义。第二件事是下标体系。是 0-based 还是 1-based我强烈建议 DP 表的行列下标从 1 开始把第 0 行和第 0 列留给空串或空段代码里写 dp[i-1][j-1] 的时候不容易搞混。代价是访问原数组要写 a[i-1]但这笔账很划算。第三件事是数据规模。最大子段和如果是 n ≤ 2×10^5那只能 O(n) 或 O(n log n)LCS 如果 n、m 都在 10^3 量级O(nm) 完全够但如果题目给的是两个排列、n 到 10^5那 O(nm) 必爆得换思路。规模决定算法选型这一步偷懒后面重写的时间成本更高。注意别一上来就套记忆里的模板。先花两分钟确认这三件事比写完发现题意理解错了再推倒重来要快得多。2. 最大子段和从三层循环到一次遍历的瘦身过程2.1 先把题目边界抠干净非空还是可空最大子段和的标准表述是给一个整数序列找出一个连续的子段使它的和最大。这里连续是硬约束子段至少包含一个元素是常见约定也就是非空。非空带来的最直接后果是如果数组全是负数答案是其中最大的那个负数而不是 0。这个结论看起来很朴素但实际写代码时特别容易翻车因为很多人脑子里默认不选就是 0。还有一种变体是允许空段这时候全负数数组答案就是 0。判断方法很简单看题目描述里有没有可以为空或至少包含一个数。如果没有明确说默认非空。我踩过一次典型的坑某道题我按允许空段的思路写了ans max(0, ...)结果全负数测试点直接错。后来养成习惯函数命名上直接把语义写出来比如max_subarray_nonempty这样调用的时候不会记混。2.2 状态定义是怎么一步步想出来的先用最笨的办法想枚举左端点 l 和右端点 r把中间加起来。这是 O(n^3)n 到 100 就跑不动了。第一步优化预处理好前缀和区间和变成 O(1)整体降到 O(n^2)。n 到 5000 勉强能过再大就不行了。想再降就得换个角度不要枚举区间而是从左往右扫过去边扫边维护一些信息。扫到第 i 个元素时考虑所有以 i 结尾的子段。这些子段分成两类只有 a[i] 一个元素的和以 i-1 结尾的某个子段再接上 a[i]。要让第二类和最大显然应该挑以 i-1 结尾的最大子段和来接。于是状态就定出来了dp[i] 以 a[i] 结尾的最大子段和转移方程随之而来dp[i] max(a[i], dp[i-1] a[i])初值是dp[0] a[0]。最终答案是max(dp[0..n-1])因为最大子段可能以任何一个位置结尾不是必须以最后一个元素结尾。这个推导过程里有一个隐含前提如果 dp[i-1] 是负数那么接上它只会拖后腿不如另起一段。这一步就是整个算法的灵魂也是很多人知道代码但讲不出为什么的地方。2.3 三版代码对照与实测我把三个版本都写出来你可以直接跑感受一下差距。第一版纯暴力枚举加求和def max_subarray_brute(a): n len(a) best a[0] for i in range(n): for j in range(i, n): s sum(a[i:j1]) # 每次重新求和浪费 best max(best, s) return best这段代码在 n 200 时大约要跑几十万次加法n 到 1000 就明显卡了。第二版前缀和优化def max_subarray_prefix(a): n len(a) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] a[i] best a[0] for i in range(n): for j in range(i 1, n 1): best max(best, pre[j] - pre[i]) return best这里语义上更接近枚举左端点 i再枚举右端点 j只是区间和用前缀和查表。复杂度 O(n^2)。第三版Kadane 算法也就是标准解def max_subarray(a): cur best a[0] for x in a[1:]: cur max(cur x, x) # 接上还是另起 best max(best, cur) return best这里cur就是滚动后的 dp[i]best就是全局答案。整个循环只做两次比较和一次加法n 10^6 也就几十毫秒的事。我第一次从 O(n^2) 改成 O(n) 的时候心里是有怀疑的这么简单的循环真的对吗后来自己手动跑了几组数据包括全负数、单元素、交替正负这些情况才彻底服气。手动模拟一遍的过程强烈建议你也做一次尤其是记录每一步的 cur 和 best 变化比看十遍题解管用。2.4 滚动变量的空间压缩dp 数组其实完全不需要。观察转移方程dp[i] 只依赖 dp[i-1]前面所有值都用不上了。所以用一个变量cur滚动就行空间从 O(n) 降到 O(1)。这里有个细节值得说虽然我们只保留了最新的 dp 值但答案不能跟着滚动掉因为最大子段不一定以最后一个元素结尾。所以必须单独用一个best变量实时更新。很多人压缩空间的时候顺手把 best 也搞没了最后返回 cur那就错了。如果题目还要求输出这个子段本身起点和终点下标那就不能只滚一个值了得一边更新一边记录起点。常见的做法是当cur x x时说明另起一段此时把起点更新为 i每当 best 被刷新就把当前起点和 i 存进结果变量。def max_subarray_with_index(a): cur best a[0] start cur_start 0 end 0 for i in range(1, len(a)): if cur a[i] a[i]: cur a[i] cur_start i else: cur a[i] if cur best: best cur start, end cur_start, i return best, start, end这段代码我在面试里被问到过两次考的就是空间压缩的同时还能不能还原方案。2.5 环形与二维扩展同一套思想换皮把数组首尾接起来变成环问最大子段和这是很经典的一道变体。思路分两种情况。第一种答案子段没有跨越首尾那就是普通的线性最大子段和。第二种答案子段跨越了首尾那么它相当于整个数组的和减去中间那段连续的最小子段和。因为跨越首尾的部分 总和 - 中间挖掉的部分要让结果最大就要让挖掉的部分最小。代码大概是这样def max_subarray_circular(a): total sum(a) best max_subarray(a) # 非空最大子段和 if best 0: return best # 全负数环形也只能取单个元素 cur_min mn a[0] for x in a[1:]: cur_min min(cur_min x, x) mn min(mn, cur_min) return max(best, total - mn)那个if best 0的判断就是前面说的非空带来的坑。如果全是负数total - mn 会等于 0对应什么都不取但题目要求非空所以必须特判掉。再往二维推就是最大子矩阵和。做法是枚举行的上下边界 top 和 bottom把这一段的每一列求和压成一个一维数组然后跑一次 Kadane。复杂度 O(n^2 * m)n、m 都在几百的时候可以接受。def max_submatrix(mat): n, m len(mat), len(mat[0]) best -10**18 for top in range(n): col [0] * m for bottom in range(top, n): for k in range(m): col[k] mat[bottom][k] best max(best, max_subarray(col)) return best这里的核心思想是降维把二维问题在某一维上枚举掉剩下的维度压成一维。这个套路后面在状态压缩DP里还会反复出现。3. 最长公共子序列二维DP的经典样本3.1 子序列和子串一字之差天壤之别先把概念钉死。子序列是从原串里删掉若干字符可以一个都不删后剩下的、保持原有相对顺序的序列不要求连续。子串是必须连续的一段。举例子abcde 和 ace 的公共子序列但 ace 不是 abcde 的子串。abcde 和 bc 的关系里bc 两者都算。这个区别直接决定状态转移。求最长公共子序列时字符 a[i-1] 和 b[j-1] 不相等我们还能跳过其中一个继续往前比求最长公共子串时一旦不相等当前这一段就断了必须清零重来。很多新手写 LCS 时把else分支写成dp[i][j] 0那就变成求最长公共子串了题目要求一变答案直接差一大截。这个错误我在帮人看代码时见过不下十次。3.2 dp[i][j] 的语义与转移推导状态定义dp[i][j]表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子序列长度。推导按 a[i-1] 和 b[j-1] 是否相等分两路。如果相等这两个字符可以直接配成一对放在公共子序列的末尾那么长度就是dp[i-1][j-1] 1。这里有个常见疑问凭什么相等就一定配上会不会不配上反而更长答案是不会因为配上之后新增的这个字符在最末尾不影响前面的任何选择属于白赚一个。如果不相等那么 a[i-1] 和 b[j-1] 至少有一个不在最终的公共子序列里。于是考虑三种情况a[i-1] 不参与答案取 dp[i-1][j]b[j-1] 不参与答案取 dp[i][j-1]两个都不参与答案取 dp[i-1][j-1]。第三种情况被前两种包含因为 dp 值单调不减所以只需要取前两个的最大值。转移方程dp[i][j] dp[i-1][j-1] 1 若 a[i-1] b[j-1] dp[i][j] max(dp[i-1][j], dp[i][j-1]) 否则初值dp[0][j] dp[i][0] 0对应空串和任何串的公共子序列长度都是 0。答案是dp[n][m]。注意这里和最大子段和不同LCS 的答案就在右下角因为我们要的本来就是两个完整串的结果。3.3 代码实现与路径回溯基础版def lcs_length(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[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[n][m] 往回走。规则是如果 a[i-1] b[j-1]这个字符属于答案记录它然后 i 和 j 同时减一否则比较 dp[i-1][j] 和 dp[i][j-1]往大的那边走。def lcs_path(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) res [] i, j n, m while i 0 and j 0: if a[i-1] b[j-1]: res.append(a[i-1]) i - 1 j - 1 elif dp[i-1][j] dp[i][j-1]: i - 1 else: j - 1 return dp[n][m], .join(reversed(res))回溯时那个和的取舍会决定当两条路径长度相同时走哪条。两种都能得到合法答案但如果不小心写成并配错方向就可能出现死循环或者长度对不上。我个人的习惯是统一往上优先即dp[i-1][j] dp[i][j-1]时让 i 减一这样得到的解更稳定方便对拍。3.4 滚动数组优化的正确姿势二维 dp 表在 n、m 都到 5000 的时候就是 2500 万个格子即使存 short 也要几十 MB很多题的内存限制扛不住。优化思路是用两行滚动更进一步压成一行加一个变量。观察转移dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。这三个分别对应左上、上、左。用一行数组row在更新 row[j] 之前row[j] 存的是上一行的 dp[i-1][j]上row[j-1] 已经被更新成 dp[i][j-1]左而左上那个值会被 row[j] 覆盖掉所以必须用临时变量提前存起来。def lcs_rolling(a, b): n, m len(a), len(b) row [0] * (m 1) for i in range(1, n 1): prev 0 # 相当于 dp[i-1][0] for j in range(1, m 1): tmp row[j] # 保存 dp[i-1][j] if a[i-1] b[j-1]: row[j] prev 1 else: row[j] max(row[j], row[j-1]) prev tmp # 给下一列当左上 return row[m]这段代码我第一次写的时候错了两次。第一次忘了更新 prev第二次把 prev 的赋值放在了 if 之前导致匹配分支拿到的不是 dp[i-1][j-1]。后来我养成了一个习惯在代码旁边手写一遍三个角色的对应关系上 row[j] 旧值左 row[j-1] 新值左上 prev对照着敲基本一次就对。注意滚动数组省了空间但丢掉了完整的 dp 表也就没法回溯路径了。如果题目要求输出具体方案要么保留完整表要么另用别的方式记录决策。3.5 相邻变体最长公共子串与编辑距离最长公共子串的转移稍有不同相等时dp[i][j] dp[i-1][j-1] 1不相等时直接归零。答案是所有 dp[i][j] 里的最大值而不是右下角。这一点和最大子段和一样属于答案在全局的类型。def longest_common_substring(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] best 0 for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 best max(best, dp[i][j]) return best编辑距离又是同一族里的另一个成员转移是三种操作的取最小值def edit_distance(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] i for j in range(m 1): dp[0][j] j for i in range(1, n 1): for j in range(1, m 1): cost 0 if a[i-1] b[j-1] else 1 dp[i][j] min( dp[i-1][j-1] cost, # 替换 dp[i-1][j] 1, # 删除 dp[i][j-1] 1 # 插入 ) return dp[n][m]把这三个放在一起看你会发现二维序列DP的基本套路就是在 (i-1, j)、(i, j-1)、(i-1, j-1) 这三个格子里做文章具体怎么组合取决于题目允许什么操作、问的是什么。4. 完整落地两道题的实测与调试记录4.1 最大子段和整套代码与用例我平时写这类函数会顺手带一段自测把边界情况全覆盖上。def max_subarray(a): cur best a[0] for x in a[1:]: cur max(cur x, x) best max(best, cur) return best if __name__ __main__: cases [ ([1, -2, 3, 10, -4, 7, 2, -5], 18), ([-2, -1, -3], -1), ([5], 5), ([0, -1, 2, -3, 4], 4), ([-1, 0, -2], 0), ] for arr, expect in cases: got max_subarray(arr) print(arr, got, got, expect, expect, OK if got expect else FAIL)第二组[-2, -1, -3]就是专门用来打非空这个点的答案是 -1 而不是 0。第五组[-1, 0, -2]是混合了 0 的情况答案是 0因为单独取那个 0 就是合法子段。这几组数据看着简单但它们覆盖了全正、全负、含零、单元素、正负交替。我建议任何人写完这个函数都拿这几组跑一遍比随手造数据靠谱。4.2 LCS整套代码与用例def lcs_path(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) res [] i, j n, m while i 0 and j 0: if a[i-1] b[j-1]: res.append(a[i-1]); i - 1; j - 1 elif dp[i-1][j] dp[i][j-1]: i - 1 else: j - 1 return dp[n][m], .join(reversed(res)) if __name__ __main__: tests [ (abcde, ace, 3), (abc, abc, 3), (abc, def, 0), (, abc, 0), (bl, yby, 2), ] for a, b, exp in tests: ln, path lcs_path(a, b) ok OK if ln exp else FAIL print(f{a!r} vs {b!r} - len{ln} path{path!r} {ok})(bl, yby)这组比较有意思两个串没有相同字符答案 0回溯时应该一个字符都不输出。空串那组用来验证初值处理如果 dp 表开成 n×m 而不是 (n1)×(m1)这里会直接抛下标越界。4.3 大输入规模下的适配从 O(nm) 到 O(n log n)前面说了LCS 的 O(nm) 在 n、m 到 10^3 甚至 10^4 的时候都没问题但题目一旦给到 10^5就必须换思路。最典型的是在线评测平台上那道经典的 P1439 模板题给两个 1 到 n 的排列求最长公共子序列。关键突破口在于两个串都是排列元素互不相同。那么我们可以把第一个排列中的每个值映射成它的位置下标然后拿第二个排列去查这些下标得到一个下标序列。求这两个排列的 LCS等价于求这个下标序列的最长上升子序列。为什么等价因为公共子序列要求两个串里都出现且在两个串中的相对顺序一致。第一个串里的顺序就是下标自然序所以第二个串里的元素要按照在第一个串中出现的先后排列也就是下标严格上升。于是问题转成了 LIS。LIS 有 O(n log n) 的解法用二分维护一个最小尾部数组import bisect def lcs_permutation(a, b): n len(a) pos [0] * (n 1) for idx, v in enumerate(a): pos[v] idx seq [pos[v] for v in b] tails [] for x in seq: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)这里的tails[k]表示长度为 k1 的上升子序列中最小的末尾元素。这个数组本身是严格递增的所以可以二分。这道题的转换思路我印象特别深因为它示范了一件事很多看起来必须 O(nm) 的问题换个等价描述就能降一个量级。4.4 小数据对拍省时间的验证方式写完 O(n) 的 Kadane 或者滚动的 LCS 之后我心里的第一反应不是应该对了而是找个可信版本对拍一下。做法是写一个明显正确但很慢的版本比如 O(n^3) 的暴力随机生成几百组小数据两个版本跑同样的输入比对结果。import random def check_max_subarray(rounds500): for _ in range(rounds): n random.randint(1, 8) arr [random.randint(-10, 10) for _ in range(n)] fast max_subarray(arr) slow max(arr[i:j1] and sum(arr[i:j1]) for i in range(n) for j in range(i, n)) # 上面这行写法不严谨实际用嵌套循环更清楚 if fast ! slow: print(mismatch, arr, fast, slow) return print(all passed)对拍这个习惯值多少钱我自己算过它能挡掉我至少一半的低级错误尤其是边界和下标类的问题。写对拍只要五分钟找 bug 可能要半小时账很好算。5. 常见问题与排查技巧实录5.1 三类高频翻车现场第一类是状态定义和答案位置不匹配。最大子段和的 dp 定义在以 i 结尾答案就必须扫一遍所有 dp 取最大最长公共子串同理。如果你直接返回 dp[n] 或者 dp[n][m]在答案不以末尾结尾的题上必错。判断方法很简单问自己一句最优解一定在最后一个位置吗不是的话就必须全局取max。第二类是边界语义没对齐。全负数数组返回 0 还是返回最大负数取决于题目允许不允许空。这个错误特别隐蔽因为大部分测试数据都是正负混合恰好能过只有专门的全负数测试点会挂。我现在的习惯是写完先在脑子里过一遍全负数、全正数、含零、单元素、两个空串这五组。第三类是空间优化时把依赖关系搞乱。滚动数组里dp[i-1][j-1] 这个左上的值是最容易被覆盖的必须用临时变量提前存。LCS 滚动那版我第一次就栽在这上面。排查方法是把行和列的语义写在注释里逐个对照row[j]旧值、row[j-1]新值、prev分别代表哪个格。5.2 问题速查表现象大概率原因处理方式答案总是比预期小状态定义是以 i 结尾忘了全局取 max循环里持续更新 best全负数数组返回 0允许空段和非空段语义混淆明确题目要求非空时不与 0 取 maxLCS 长度明显偏小else 分支写成了清零退化成求子串改回取 max(dp[i-1][j], dp[i][j-1])结果对但不稳定回溯时相等路径的选择不一致固定优先级比如统一优先往上走内存超限二维表全开改滚动数组或存 short大数据超时O(nm) 扛不住 10^5排列场景转 LIS用 O(n log n)下标越界dp 表开成 n×m统一开 (n1)×(m1)0 行 0 列做哨兵环形题输出 0全负数时 total - min 得到空集特判 best 0 直接返回 best这张表里的每一条我要么自己踩过要么在别人的代码里见过不是凭空列的。5.3 我个人踩过的几个坑第一个坑是想当然的空间压缩。有段时间我看 LCS 的二维表不顺眼动手改成滚动数组结果写完直接错了。后来复盘发现我改的时候脑子里想的是只需要上一行但忘了 dp[i][j-1] 是本行新算出来的值这个依赖是左边。二维 DP 的滚动永远是上一行 当前行已经算出来的部分这一点想清楚了再动手能少很多返工。第二个坑是用 0 当作不可达标记。最大子矩阵和那道题里如果初始 best 设成 0遇到全负矩阵就会输出 0而正确答案是最小的那个负数。那之后我一律用-10**18这种明确不可达的值做初值虽然丑一点但不骗自己。第三个坑是对拍数据分布太单一。早期我造对拍数据都用random.randint(-10, 10)结果全是正负混合全负数的情况几乎撞不上。后来改成有意识地混入全负、全零、单元素这些边界才真正起到防护作用。数据造得随机不代表覆盖得全面。6. 这两个模型还能往哪延展6.1 最大子段和的线段树版本如果题目要求支持单点修改再查询区间最大子段和Kadane 就不够用了得请线段树出场。每个节点维护四个值区间和sum、最大前缀和pre、最大后缀和suf、区间最大子段和best。合并两个子节点时sum l.sum r.sum pre max(l.pre, l.sum r.pre) suf max(r.suf, r.sum l.suf) best max(l.best, r.best, l.suf r.pre)这四个式子背后的逻辑都很直白。比如pre要么完全落在左区间里要么覆盖整个左区间再延伸到右区间两种情况取大。best则要么在左边、要么在右边、要么跨中间左后缀 右前缀。单点修改和区间查询都是 O(log n)整体 O(n log n) 建树加 O(log n) 每次操作。我在做一道带修改的区间最大子段和题时一开始想用分块糊过去结果写了两百多行还过不了换成线段树之后代码短了一半效率还高。这个结构值得专门花时间掌握。6.2 和背包问题在思维上的互通有人觉得序列DP和背包DP是两套东西其实底层思维方式是一致的都是在某个位置做决策决策影响后续状态。背包问题的 dp[i][j] 表示前 i 个物品、容量 j 下的最大价值转移是选或不选LCS 的 dp[i][j] 表示前 i 个和前 j 个字符下的最长公共子序列转移是匹配或不匹配。共同点在于状态里包含了处理到哪了这个进度信息转移就是在当前位置做一次选择。背包的一维滚动和 LCS 的滚动数组本质也是同一件事——把只依赖上一层的维度压掉。学完这两个模型再去写 01 背包很多人会发现原来那些倒序枚举容量的技巧和 LCS 里保存左上值的技巧是同源的。顺带提一句动态规划在工程侧的应用也很广比如资源调度、路径规划、库存分配这类问题本质上都是分阶段决策 状态转移的模型只是状态空间比刷题时大得多工程上通常还要配合状态压缩和剪枝。6.3 后续练习路线如果这两道题你已经能独立写出来包括边界、滚动优化、路径回溯那接下来可以按这个顺序往下走先做最长上升子序列把 O(n^2) 和 O(n log n) 两版都写一遍顺便把二分的过程吃透。然后做编辑距离和最长公共子串感受同一套二维骨架的变体。再往上就是区间DP从石子合并、最长回文子序列这类题入手体会区间状态怎么定义。最后是树形DP和状态压缩把状态这个概念从数组下标扩展到集合和树节点上。每一步都别跳过对拍和边界测试。我见过太多人一路刷题一路背模板遇到变形题就懵。真正把状态定义、转移依据、空间时间优化这三件事想明白后面无论遇到什么新题型你都有办法自己推出来。最后分享一个我用了很久的小技巧每道DP题做完之后用一句话把状态定义写下来贴在代码注释第一行。比如dp[i] 表示以 i 结尾的最大子段和。这句话写不出来说明状态没想清楚写出来了但代码跟它对不上说明转移写错了。这个习惯帮我在复盘时省了大量时间也让我后来给别人讲题时能张口就说清楚每一个下标在干什么。