1. 这两个问题为什么值得放在一起讲最大子段和和最长公共子序列这两个题几乎出现在所有动态规划入门路线的同一个位置上。不是因为它们难度接近而是因为它们各自代表了一类状态设计的范式前者是单序列线性 DP教你状态怎么挂到一个位置身上后者是双序列二维 DP教你两个指针怎么同时往前走。把这两道题吃透再看 01背包、编辑距离、最长上升子序列这些题会发现套路其实是同一套骨架换了几块零件。先说清楚它们分别解决什么问题。最大子段和也常被叫最大连续子数组和、最大区间和处理的是给一个可能含负数的数组找出一个连续区间让区间内元素之和最大。最长公共子序列LCS处理的是给两个序列找出它们共同拥有的、不需要连续但必须保持相对顺序的最长子序列返回长度或者具体方案。前者的实际应用包括股票最大收益区间、信号里的最强连续段、日志里连续异常区间的统计后者覆盖了文本相似度、代码 diff、DNA 序列比对、版本控制里的差异比较。适合谁看如果你已经会写递归和循环但一遇到状态怎么定义就卡住那这篇就是冲着你写的。我会把每一步为什么这么设计讲清楚而不是丢一个转移方程让你背。代码统一用 Python因为它写起来短能把注意力留在逻辑上但最后的性能优化和对拍验证部分思路对 C 和 Java 完全适用。刷题平台上常说的01背包动态规划python洛谷最长公共子序列动态规划dp算法讲解本质上讲的是同一批底层思路本文会把它们内在的联系一并串起来。2. 最大子段和把以 i 结尾写进状态里2.1 为什么用前 i 个元素定义状态会直接卡死大多数人第一次做这题直觉是定义dp[i]表示前 i 个元素里的最大子段和。这个定义看起来很自然但转移时会立刻发现走不通。原因是前 i 个元素的最优解可能根本没用到第 i 个元素也可能用到了第 i 个元素但以第 i 个元素结尾的那一段的具体和值你并不知道。你手上缺的是一份接力棒没法判断要不要把第 i 个元素接上去。换成dp[i]表示以第 i 个元素结尾的最大子段和问题一下就顺了。因为你强制要求这段必须包含a[i]那么它的上一段要么不存在自己单独成段要么就是以 i-1 结尾的最优段再接上a[i]。这就是状态定义的全部意义把未来需要什么信息提前钉死在状态里。def max_subarray(nums): best dp nums[0] # dp 表示以当前元素结尾的最大和 for x in nums[1:]: dp max(x, dp x) # 要么另起炉灶要么接上前面 best max(best, dp) return best这段代码就是常说的 Kadane 算法时间复杂度 O(n)空间 O(1)。注意dp在这里是滚动的——我们只需要上一轮的值所以不需要开数组。这是个很典型的信号转移只依赖前一项时数组就可以退化成变量。2.2 转移方程背后的取舍什么时候该断dp max(x, dp x)这一行是整个算法的灵魂拆开看就是一次二选一的决策。如果dp前面那段的和是正数那把它接上显然更划算因为前面的积累能帮我抬高当前的和。如果dp是负数或者零那接上它只会拖后腿不如从当前这个元素重新开始一段。你可以理解为手里拿着一段历史包袱正的就继续背负的立刻扔掉。这个判断看起来和贪心很像但性质不同。它之所以正确是因为我们枚举了所有以 i 结尾的段并且每一轮都做到了最优满足最优子结构。而纯贪心的问题是它可能因为某一步的局部最优错过后面更长但需要先忍一段负数才能拿到的更大收益。DP 不担心这个因为它保留了以 i 结尾这个精确的位置信息。注意best必须在循环内部同步更新不能只在最后取dp的值。因为最优段不一定在数组末尾结束这一点是全负数数组最容易暴露的地方。2.3 全负数数组是第一个照妖镜如果数组是[-3, -1, -2]正确结果应该是-1题目要求非空子段。上面这段代码能过初始dp -3, best -3第二轮dp max(-1, -4) -1best更新为-1第三轮dp max(-2, -3) -2best保持-1。答案正确。但如果题目额外允许子段可以为空那答案应该至少是 0。这时候需要在最后加一句return max(best, 0)。这两种设定的区别在刷题时经常被忽略导致同样的代码在一个平台上 AC、在另一个平台上 WA。所以拿到题目先看清子段是否允许为空。另外提醒一个细节初始化best和dp时不要用0。一旦用 0 初始化全负数组就会输出 0直接错掉。用nums[0]是最稳的写法。2.4 换一条路前缀和的最值做法最大子段和还有一个完全不依赖 DP 的解法用前缀和的性质推出来设pref[i] a[0] ... a[i]那么任意区间(l, r]的和等于pref[r] - pref[l]。要让这个差值最大就要在固定的r处找到它左边最小的pref。def max_subarray_prefix(nums): pref 0 min_pref 0 best -10**18 for x in nums: pref x best max(best, pref - min_pref) # 先算答案 min_pref min(min_pref, pref) # 再更新最小值 return best这里有两个坑值得单独说。第一min_pref必须初始化为 0它代表从头开始的那一段对应的前缀这样pref - 0才表示从第一个元素到当前的整段和。第二必须先用当前的min_pref算答案再把它本身纳入最小值。如果顺序反了pref - min_pref就会取到pref - pref 0等于悄悄允许了空段全负数数组就会输出 0。这个顺序问题是这段代码里最容易写错、最难看出的一处。解法时间复杂度空间复杂度直观程度适合场合双重循环暴力O(n²)O(1)最高验证小数据、对拍基准分治O(n log n)O(log n)中等教学演示跨中点思想Kadane DPO(n)O(1)高正式提交、工程使用前缀和最值O(n)O(1)中等需要顺手维护前缀的场景分治版本顺带提一下思路它也是理解这道题的一个很好角度把区间从中间劈开答案只可能完全落在左半边、完全落在右半边、或者跨越中点。跨越中点的那部分可以从中点向两边扫分别求向左最大后缀和和向右最大前缀和两者相加。这个跨界处理的套路在后面的最大子矩阵和里会再次用到。3. 最长公共子序列二维表是怎么一格一格填满的3.1 状态定义的前提只看两个序列的末尾LCS 的状态定义是dp[i][j]表示序列 A 的前 i 个字符与序列 B 的前 j 个字符的最长公共子序列长度。定义完先问一句这个状态能不能推出下一步考虑两个末尾字符a[i]和b[j]。只有两种情况。如果它们相同那么它们一定可以被放进公共子序列的末尾因为把两个相同的字符同时配对不会破坏前面任何已有的配对顺序所以dp[i][j] dp[i-1][j-1] 1。如果它们不同那么这两个字符里至少有一个不会出现在最终的公共子序列中于是dp[i][j]就取丢掉 a 的末尾和丢掉 b 的末尾两种情况里的较大值max(dp[i-1][j], dp[i][j-1])。这里有个常被问到的问题为什么两个末尾不同的时候不需要考虑两个都丢掉的情况因为dp[i-1][j]和dp[i][j-1]的答案本身就已经覆盖了那个结果——它们各自包含了更小的子问题dp[i-1][j-1]不大于这两者的任意一个。这是不漏解的证明要点也是很多人误以为转移方程少了分支的原因。3.2 完整实现与填表过程def lcs(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的大小是(n1) x (m1)多出来的第 0 行和第 0 列代表空序列全部为 0这就是天然的边界条件。而访问原字符串时用的是a[i-1]、b[j-1]因为第 i 个字符对应的是下标 i-1。这个DP 表从 1 开始、字符串从 0 开始的错位是这类题写错下标的首要来源。拿a abcbdab、b bdcaba举例跑完之后dp[7][6] 4对应的一个公共子序列是bcba。注意一个这两个字——最长公共子序列往往不唯一比如abc和acb的 LCS 长度是 2答案是ab或ac都合法。所以如果题目只要求长度就不要在方案本身上较劲。复杂度方面时间 O(nm)空间 O(nm)。1000 乘 1000 的输入就是一百万个格子Python 里用嵌套列表大概占几十 MB能跑但不算轻快到 5000 乘 5000 就是两千五百万个格子这时候二维数组就非常吃力了必须做空间压缩。3.3 把具体方案回溯出来只求长度的题是一半很多场景还需要知道到底哪些字符对上了比如 diff 工具要标出具体差异位置。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 .join(reversed(res))回溯的方向必须和填表方向相反填表是从左上往右下推回溯就是从右下往左上退。遇到相同字符就收下这个字符并同时退一格不同的时候往值更大的那个邻居走。这里和的选择会决定拿到哪一条合法方案两个都对只是结果可能不同。别看到换了符号结果变了就以为有 bug。4. 滚动数组把二维 LCS 压到一维的完整推演4.1 为什么直接把二维砍成一维会出错观察转移方程dp[i][j]只依赖三个值dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。也就是说第 i 行的计算只需要第 i-1 行的数据这就有压缩空间了。最粗暴的想法是只开一个长度m1的一维数组dp外层循环枚举 i、内层枚举 j一边算一边覆盖。但直接写会出问题当你在第 i 行计算dp[j]时dp[j]里存的是上一行i-1的值这正好是想要的但dp[j-1]已经被这一轮更新过了它是本行i的值这个也对。唯独dp[i-1][j-1]丢了——它原本在dp[j-1]的旧位置上被覆盖掉了。所以关键在于用一个变量把这个被覆盖掉的旧值手动接住。4.2 正确的写法与变量含义def lcs_1d(a, b): if len(b) len(a): a, b b, a n, m len(a), len(b) dp [0] * (m 1) for i in range(1, n 1): diag 0 # 保存 dp[i-1][j-1] ai a[i - 1] for j in range(1, m 1): tmp dp[j] # 先把 dp[i-1][j] 存下来下一轮它就是 dp[i-1][j-1] if ai b[j - 1]: dp[j] diag 1 elif dp[j] dp[j - 1]: dp[j] dp[j] # 沿用 dp[i-1][j] else: dp[j] dp[j - 1] # 用本行已经算好的 dp[i][j-1] diag tmp return dp[m]这段代码只有二十行但diag和tmp的配合是整个优化里最需要想明白的地方。tmp在更新dp[j]之前先读出旧值这个旧值是dp[i-1][j]而它恰好就是下一轮 j1 需要的dp[i-1][(j1)-1]也就是diag。所以每次循环末尾把tmp交给diag链条就接上了。可以在纸上画两行表格手动走一遍aab、bba跑完就会彻底理解。外层交换a和b的那两行是有意为之一维数组的长度是m1也就是内层循环的长度。让较短的序列当b数组就更短内存更省缓存命中率也更好。这类按维度小的方向压的做法在双序列 DP 里是通用技巧。4.3 一维和二维的实际差别规模 (nm)二维数组内存一维数组内存备注1000约 10^6 个整数约 10^3 个整数两者都轻松5000约 2.5×10^7 个整数约 5×10^3 个整数二维开始吃紧20000约 4×10^8 个整数约 2×10^4 个整数二维基本不可行时间上两者都是 O(nm)一维版本通常会更快一些原因不是算法复杂度变了而是每次只在一小段连续内存上读写缓存友好得多。不过要注意一维版本没法回溯方案因为历史行都被覆盖了。如果题目要求输出具体的公共子序列就只能用二维数组或者额外记录每个状态的选择方向额外一份 O(nm) 的空间等于没省。这是空间优化里必须提前想清楚的取舍。5. 踩坑实录调试这两类题的常见翻车点5.1 答案的取值位置写错最大子段和里best忘了在循环内更新这是新手最常犯的错。表现很典型样例里答案刚好在末尾代码能过一换成最大值出现在中间的数据就 WA。判断方法很简单自己构造一个[5, -10, 8, 0, 0]正确答案是 8如果你只取末尾的dp会得到 0。LCS 里对应的坑是把答案写成max(dp[n])或者dp[0][m]。正确的是dp[n][m]因为dp[n][m]表示两个完整序列的 LCS而 LCS 天然单调不减右下角一定是全表最大值。顺带说正因为这个单调性dp[n][m]才可以直接当作答案不需要再扫一遍表。5.2 空输入和单元素输入nums为空时Kadane 的第一行nums[0]会直接抛异常所以要在函数开头加一个长度判断。这类题在面试里被问到时边界处理往往是评分点之一。LCS 里空串的坑相对隐蔽一些。a为空、b为abc时dp是 1 行 4 列循环range(1, 1)直接不进返回dp[0][3] 0结果正确。但一维版本在交换之后要小心 n 和 m 的重算a, b b, a之后必须重新取n, m len(a), len(b)如果还沿用交换前的值数组长度就和内层循环对不上直接索引越界。5.3 字符还是数字统一类型很关键LCS 的模板对字符和整数都适用因为只用到了比较相等。但混着来就会出事b[j-1]如果是从字符串里取的字符而a是整数列表比较永远为假你得到的会是 0还以为是逻辑写错了。调试时先打印两个序列的前几个元素确认类型一致。另外当元素不是简单字符而是字符串、元组这类对象时比较的开销会显著上升。这时候一个有用的工程技巧是对元素做离散化比如映射成整数 ID把比较成本降下来。5.4 用暴力对拍替代肉眼盯代码动态规划的调试靠读代码效率很低因为状态表是二维的人脑模拟几十格就开始出错。正确做法是写一个暴力版本做对拍。import random from itertools import combinations def is_subseq(s, b): i 0 for ch in b: if i len(s) and ch s[i]: i 1 return i len(s) def brute_lcs(a, b): best 0 for r in range(len(a) 1): for idx in combinations(range(len(a)), r): s [a[i] for i in idx] if is_subseq(s, b): best max(best, r) return best for _ in range(2000): a .join(random.choice(abc) for _ in range(random.randint(0, 8))) b .join(random.choice(abc) for _ in range(random.randint(0, 8))) assert lcs(a, b) brute_lcs(a, b), (a, b)暴力版本不用追求效率只追求绝对正确和好写好懂。字母表选abc是故意的字母种类少随机串里重复字符多、各种分支都能被覆盖到比用 26 个字母更容易触发 bug。这个缩小字母表提高覆盖密度的小技巧在字符串类题目对拍里非常好用。最大子段和的对拍同理用双重循环暴力当基准随机数组里混入 0 和负数。6. 从这两个模板长出来的常见变种6.1 环形最大子段和问题变成数组首尾相接成环求最大和。思路是把答案分成两类要么最优段没有跨过接缝那就是普通的最大子段和要么跨过了接缝这时候它在环上的补集刚好是一段中间连续的最小区间答案是总和减去最小子段和。def max_subarray_circular(nums): total sum(nums) max1 max_subarray(nums) if max1 0: return max1 # 全负数不能取总和减最小段 min1 -max_subarray([-x for x in nums]) return max(max1, total - min1)max_subarray([-x for x in nums])求的是取反后的最大子段和再取负就得到原数组的最小子段和。那个if max1 0的分支不能省全负数时总和减最小子段和会把整段都排除掉得到 0而题目要求非空子段必须直接返回max1。6.2 最大子矩阵和把二维矩阵压成一维是最大子段和最漂亮的一次迁移。做法是枚举上下边界top和bottom把这两个边界之间的每一列纵向求和得到一个一维数组然后对这个小数组跑一次 Kadane。枚举上下边界是 O(rows²)每次求和可以增量维护整体复杂度 O(rows² × cols)。def max_submatrix(mat): rows, cols len(mat), len(mat[0]) best -10**18 for top in range(rows): col_sum [0] * cols for bottom in range(top, rows): for c in range(cols): col_sum[c] mat[bottom][c] # 增量累加避免重复求和 best max(best, max_subarray(col_sum)) return best这里col_sum用增量累加而不是每轮重算是把 O(rows³ × cols) 降到 O(rows² × cols) 的关键。这个固定左边界、增量维护右边界的降维思路和滑动窗口类的题目是共通的。6.3 三个近似模板的对照学到这里容易把几个相似题目搞混用一张表区分开问题状态定义转移要点答案位置最长公共子序列dp[i][j]前 i、前 j 的 LCS相同 1不同取两方向最大dp[n][m]最长公共子串dp[i][j]以 i、j 结尾的公共子串相同dp[i-1][j-1]1不同归 0全表最大值编辑距离dp[i][j]前 i 转成前 j 的最少操作增、删、改三种取最小dp[n][m]01 背包dp[i][j]前 i 件物品容量 j 的最大价值选或不选容量维度倒序压一维dp[V]看到没最长公共子串和 LCS 只差一个不同的时候归 0但答案取值位置就完全不同了因为子串必须连续最优解不一定在末尾结束。这个差别和最大子段和里best要循环内更新是同一个道理。而 01 背包的一维压缩要求容量维度倒序遍历原因也是为了避免同一件物品被重复选——它和 LCS 一维压缩的顺序不能反是同一类问题的两种表现。7. 在刷题平台上验证思路的节奏建议模板写出来只是第一步真正掌握是在平台上把边界数据挨个过一遍。以最大子段和为例P1115这类模板题的数据里通常会有全负数、单元素、有零、正负交替等情形正好一次性把前面提到的坑都踩出来。建议的提交顺序是先交暴力版确认理解正确再交 DP 版两个版本都过了说明状态定义没问题如果 DP 挂了而暴力过问题一定在转移或者答案取值位置。洛谷上那道把 LCS 和 LIS 串起来的题P1439很值得单独做一遍。它的特殊之处在于两个序列都是 1 到 n 的排列于是可以把第一个序列映射成它的下标把第二个序列的每个数替换成对应的下标问题就变成了求这个下标序列的最长上升子序列用二分加贪心的 O(n log n) 做法就能过掉 n 到 10 万级别的数据。这道题的启发在于不要一看到 LCS 就条件反射地开二维数组先看看输入有没有额外的结构可以利用。二维 DP 的 O(nm) 在排列问题上会被卡得很死。一个我自己一直在用的验证流程分享给各位写完模板后先用手算的小数据走一遍表确认填表方向和第二行的值再写对拍脚本跑 2000 组随机数据最后才是提交平台。手算这一步看着笨但它能在三十秒内发现a[i-1]还是a[i]这种一秒钟就能改、但要花二十分钟调试的低级错误。另外把两个版本Kadane 与前缀和、二维与一维都实现一遍然后互相对拍也是检验自己是否真的理解了空间优化的好办法——如果能解释清楚一维版本里diag为什么要存在那这块知识基本就长在身上了。