最长公共子序列Longest Common Subsequence简称 LCS在信息学奥赛一本通里是编号 1265 的例 9.9几乎每个学动态规划的人都会在这里卡一下。前面做的数字三角形、最长不下降子序列状态都挂在“一条线”上到了这题突然变成两个序列、二维状态很多人第一反应是不知道 dp 数组该怎么开。其实它的骨架特别朴素两个指针各自在一个序列上走能配上就一起往前挪一格配不上就让其中一个多走一步再试。这篇文章我不打算只贴一份能过的代码而是把状态怎么想出来的、转移为什么必须这么写、边界为什么这么设、空间怎么压一步一步拆开讲清楚。不管你刚学 DP 还是刷题刷到想复习跟着走一遍应该都能把这道题吃透。1. 先搞清楚题目到底在问什么1.1 子序列和子串差的就是“连续”两个字题目原文的表述大概是这样的一个给定序列的子序列是在该序列中删去若干元素后得到的序列。也就是说如果序列 X 是x1, x2, ..., xm那 Z 是 X 的子序列当且仅当存在一个严格递增的下标序列i1, i2, ..., ik使得对每个 j 都有X[i_j] Z[j]。公共子序列就是同时是两个序列子序列的那个 Z。而最长公共子序列就是所有公共子序列里长度最大的那个。这里最容易翻车的地方是“子序列”和“子串”混为一谈。子串要求字符在原序列里必须连续挨着子序列只要求保持相对先后顺序中间可以随便挖空。举个具体的例子X ABCBDABY BDCABABCBA是它俩的公共子序列因为它在 X 里的下标是 2、3、5、7在 Y 里的下标是 1、3、5、6两个下标序列都是严格递增的但它不是公共子串因为在 X 里这几个字符并不挨着。这个区别不是文字游戏它直接决定状态怎么设计。公共子串的 dp 含义是“以某个位置结尾”公共子序列的 dp 含义是“前缀范围内”两套写法完全不同后面第 5 节我会专门对比一次。1.2 为什么这题一眼就该锁定动态规划我见过有同学一上来想用双指针贪心两个指针都从头开始相等就都往后走不等就把其中一个往后挪。这个思路在部分数据上能过但它是错的。构造一个反例X AABY ABA。贪心从第一个字符开始A 和 A 相等都走一步接着 X 的第二个字符 A 对上 Y 的第二个字符 B不等如果策略是“挪 X”就会继续往下比 B 和 B得到长度 2 的AB如果策略是“挪 Y”会得到长度 2 的AA。两条路都能拿到 2看起来没问题但只要换一组数据错误的选择就会让你彻底丢掉最优解。根本原因在于某一位配不上时你并不知道放弃哪一个才是对的这个决定需要“全局信息”而贪心只看眼前天然拿不到。那暴力呢枚举 X 的所有子序列逐个判断在不在 Y 里。X 长度 20 的时候有 2^20 约一百万个子序列勉强能跑长度到了 1002^100 这个量级连宇宙年龄都不够用。而且暴力会大量重复计算——判断X[1..5]和Y[1..6]是否匹配和判断X[1..5]和Y[1..7]是否匹配中间有大段是重叠的。既有重叠子问题又有最优子结构大问题的最优解一定由小问题的最优解拼出来这两个特征凑齐动态规划就是标准答案。题目长度上限通常在 200 到 1000 之间O(nm)的 DP 是 4 万到 100 万级别非常轻松而指数级暴力在 n20 之后就没法看了。这也是出题人把数据范围卡在这个区间的用意。1.3 状态怎么定dp[i][j] 的含义与直觉动态规划最忌讳的就是直接把状态抄下来背。你得先回答一个问题我要比较的是两个序列哪两个“程度”是必须记住的答案是两个前缀的长度。dp[i][j]表示序列 X 的前 i 个字符也就是X[1..i]和序列 Y 的前 j 个字符Y[1..j]的最长公共子序列长度。注意这里是“前 i 个”不是“以第 i 个结尾”这两个说法在本问题里不能互换原因上面已经说过。为什么是前缀因为公共子序列是从前往后依次匹配出来的。你决定完前 i 个和前 j 个字符的情况之后第 i1 个字符怎么处理只依赖前面匹配到了哪里不依赖具体匹配的是哪几个字符。这就是“无后效性”满足它状态才立得住。下标从 1 开始写这个习惯在这题里特别值得坚持。dp[0][j]和dp[i][0]天然代表“其中一个序列是空的”答案直接是 0边界不用特判。真正对着字符串取字符的时候再用a[i-1]、b[j-1]减一就行。我见过太多人图省事从 0 开始结果dp[i-1]在 i0 时越界要么 RE 要么读到垃圾值调半天调不出来。2. 把转移方程推出来而不是背出来2.1 字符相等时的转移为什么是 dp[i-1][j-1]1假设现在算dp[i][j]两个序列各自看到最后一个字符也就是X[i]和Y[j]。如果它俩相等我的做法是把这个字符作为公共子序列的一部分配上它然后去看前面的部分X[1..i-1]和Y[1..j-1]能配多长。写成公式就是dp[i][j] dp[i-1][j-1] 1为什么这样一定最优两个方向各说一句。第一这样构造出来的解是合法的X[1..i-1]和Y[1..j-1]的一个公共子序列末尾接上这个相等的字符仍然是 X、Y 的公共子序列长度加了 1所以dp[i][j] ≥ dp[i-1][j-1] 1。第二这样做不会丢解假设X[1..i]和Y[1..j]的最优解没有用到X[i]或者没有用到Y[j]那这个解其实完全落在X[1..i-1]和Y[1..j]或者反过来的范围里。但因为X[i] Y[j]我们总可以用贪心把它俩对齐换成包含这个字符的解长度不会更差。两条合起来等号成立。我一般跟新手这么解释相等的字符是“白捡的”能捡一定要捡不存在捡了反而变差的可能。2.2 字符不等时的转移为什么取 max 就够X[i] ! Y[j]时情况麻烦一点因为最优解里这两个字符至少有一个用不上——毕竟它们不相等不可能同时出现在公共子序列的同一位置上对齐。于是只有两种可能最优解里没用X[i]那它就完全落在X[1..i-1]和Y[1..j]里面长度不超过dp[i-1][j]最优解里没用Y[j]那它就落在X[1..i]和Y[1..j-1]里面长度不超过dp[i][j-1]。两者必居其一所以最大值就是答案dp[i][j] max(dp[i-1][j], dp[i][j-1])这里有个常见的误区有人会写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][j-1]因为多加一个字不会让最长公共子序列变短——这是 dp 的单调性写进去是多余的纯粹浪费一次比较。还有个更深的误区有人想写max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]))还不够非要再减点东西这就是把 LCS 和编辑距离的转移搞混了。LCS 里不存在“代价 1”这回事只有“长度 1”。2.3 边界条件与初始化为什么第一行第一列全是 0dp[0][j]X 是空的跟任何序列的公共子序列只能是空的长度 0。dp[i][0]Y 是空的同理长度 0。所以第一行和第一列全部初始化为 0。这也是为什么强烈建议下标从 1 开始——边界不需要任何 if 判断循环里dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]永远合法。注意这个 0 边界的前提是“序列元素来自某个字符集、长度非负”。如果题目把空序列也当成合法的子序列去计算某些指标边界要另行处理。做 LCS 本身时0 就是标准答案。2.4 复杂度账本与数据规模的判断状态总数是(n1) × (m1)每个状态 O(1) 转移所以时间复杂度O(nm)空间复杂度O(nm)。拿具体数字感受一下。一本通这道题字符串长度一般不超过 200那张表是 201×201 ≈ 4 万个格子一个 int 4 字节总共 160KB 左右随便怎么开都行。如果换成某些 OJ 上 n、m ≤ 1000 的版本格子数约 100 万内存约 4MB也没压力。但要是 n、m 都到了 5000那就是 2500 万个格子、100MB 内存很多 OJ 的 64MB 或 128MB 限制就要爆了必须做滚动数组压缩这个后面第 3.4 节详细写。顺便说一句判断一道 DP 题该用什么写法最快的办法就是先把状态数和内存算一遍别上来就写。这比事后 RE 或者 MLE 再回来改要省时间得多。3. 动手实现从记忆化搜索到滚动数组3.1 先写一个能过小数据的记忆化搜索如果你对递推顺序还没感觉最稳的路子是先写记忆化搜索。它的好处是把“转移方程”直接翻译成递归不用管循环从哪边开始、哪一维在外层。#include bits/stdc.h using namespace std; string a, b; int memo[1005][1005]; // -1 表示没算过 int dfs(int i, int j) { if (i 0 || j 0) return 0; if (memo[i][j] ! -1) return memo[i][j]; if (a[i - 1] b[j - 1]) return memo[i][j] dfs(i - 1, j - 1) 1; return memo[i][j] max(dfs(i - 1, j), dfs(i, j - 1)); } int main() { cin a b; memset(memo, -1, sizeof(memo)); cout dfs(a.size(), b.size()) endl; return 0; }几个实战细节值得说。memo一定要用-1初始化而不是0因为0是一个合法的 dp 值没有公共前缀时就是 0用它当“没访问过”的标记会让记忆化完全失效程序退化成暴力还浑然不觉。另外这个递归深度最坏是n mn、m 都到 1000 的时候理论上有 2000 层某些环境下会有栈溢出的风险。所以记忆化适合用来验证思路真交题还是推荐递推。3.2 递推版本一份可以直接抄的完整代码递推就是老老实实按 i 从小到大、j 从小到大填表。因为dp[i][j]只依赖左边、上边、左上三个格子只要保证外层 i 递增、内层 j 递增用到的值一定已经算好了。#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; // 一行一个序列 int n a.size(), m b.size(); // dp[i][j]: a 的前 i 个字符 与 b 的前 j 个字符 的 LCS 长度 vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { 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]); } } cout dp[n][m] endl; return 0; }如果一本通上的原题给的是两行整数序列而不是两行字符串把string a, b换成int a[1005], b[1005]读入时先用cin n读长度再循环读数组比较那行改成a[i-1] b[j-1]即可。整张表的结构完全不用动——这类题目真正通用的部分是状态和转移不是数据类型。3.3 手工跑一遍样例把 dp 表打出来看用经典样例X ABCBDABn7Y BDCABAm6正确答案是 4比如BCBA或BDAB。我按上面的循环规规矩矩填一遍把表打出来i \ j01(B)2(D)3(C)4(A)5(B)6(A)000000001(A)00001112(B)01111223(C)01122224(B)01122335(D)01222336(A)01223347(B)0122344拿两个格子核对一下你就知道规律了。看i2, j5a[1]Bb[4]B相等所以取左上dp[1][4] 1加 1得 2。再看i4, j6a[3]Bb[5]A不等取上边dp[3][6] 2和左边dp[4][5] 3的最大值得 3。右下角dp[7][6] 4就是最终答案。我特别推荐新手手动填两行。你会发现整张表是“单调不减”的从左往右、从上往下都不会变小。一旦你写出来的表违反了这条几乎可以肯定转移写错了——这是最快的自查方法比反复读代码有效得多。3.4 空间优化滚动数组与那个容易写错的 diag 变量先想明白一件事算dp[i][j]只用到第 i-1 行和第 i 行的左边第 i-2 行以及更早的行算完就永远用不上了。所以没必要保存整张表留两行就够了。但还可以更省只留一行。思路是这样的用一维数组dp[j]代表“当前正在算的这一行的第 j 列”。那么在进入内层循环、还没覆盖dp[j]之前它保存的其实是上一行的dp[i-1][j]。而dp[j-1]因为刚刚在这一轮 j-1 时已经被更新过所以代表的是本行的dp[i][j-1]。唯一麻烦的是左上角dp[i-1][j-1]——它已经被覆盖掉了得提前存起来。#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; int n a.size(), m b.size(); if (n m) { swap(a, b); swap(n, m); } // 让短的那个当列省内存 vectorint dp(m 1, 0); // 第 0 行全 0 for (int i 1; i n; i) { int diag 0; // 相当于 dp[i-1][0]恒为 0 for (int j 1; j m; j) { int up dp[j]; // 先存下 dp[i-1][j]此刻还没被覆盖 if (a[i - 1] b[j - 1]) dp[j] diag 1; // dp[i-1][j-1] 1 else dp[j] max(up, dp[j - 1]); // max(dp[i-1][j], dp[i][j-1]) diag up; // 给下一列当左上角 } } cout dp[m] endl; return 0; }这段代码里diag是全篇最容易写错的地方值得单独讲。它的语义是“上一行的前一列”也就是dp[i-1][j-1]。每一轮开始时它应该是dp[i-1][0] 0所以在进入内层循环前把它置 0。循环体内先用up把还没被改写的dp[j]抄下来这是dp[i-1][j]然后在算完本格之后把这个up交给diag——因为下一列 j1 需要的左上角正好就是dp[i-1][j]。顺序上必须这么排先备份、再计算、最后转移 diag。少一步或者调换顺序答案就会莫名其妙地偏小。我自己第一遍写的时候就是把diag up放在了int up dp[j]前面结果所有相等的分支都少加了东西样例还能碰巧过交上去 WA 一大片。另外注意开头那句if (n m) swap(a, b)。一维数组按列的个数开让短的序列当列数组就短缓存命中率也更好。这个交换对答案没有任何影响因为 LCS 是对称的。3.5 进阶把最长公共子序列本身输出出来有些加强版题目要求输出那个序列而不是长度。这时一维数组就不够用了因为你要“往回找路”得知道每一步是从哪个方向来的。最直接的做法是保留完整的二维表然后从右下角(n, m)开始倒着走string lcs; int i n, j m; while (i 0 j 0) { if (a[i - 1] b[j - 1]) { // 这个字符属于答案 lcs.push_back(a[i - 1]); --i; --j; // 沿对角线回退 } else if (dp[i - 1][j] dp[i][j - 1]) { --i; // 答案在上面那一行里 } else { --j; // 答案在左边那一列里 } } reverse(lcs.begin(), lcs.end()); // 回溯是倒着走的翻转回来因为是从末尾往前走的收集到的字符顺序是反的最后必须reverse一次。else if里的决定了在两条路等长时优先往上走这会影响到最终输出的具体是哪一个解。如果题目要求“字典序最小的最长公共子序列”这个写法就不够了得换一套贪心先算出 dp 表然后从前往后在每个位置上枚举最小可用字符判断选了它之后能不能凑满剩余长度能选才选。那是一道独立的题这里先埋个引子。如果内存实在紧又必须要方案还有个折中办法用两位的位压缩数组记录每个格子的方向左上、上、左三种100 万格只要 250KB 左右比一个字节存方向省得多。4. 踩坑记录与常见问题速查4.1 输入输出上的坑一本通这道题的输入一般是两行每行一个序列。用cin a b就能读——cin遇到空白就断开两个string正好各接一个。但如果序列里本身可能含空格比如某些字符串题的输入带空格你就得改成getline(cin, a)读整行并且记得处理行尾那个看不见的\rWindows 下生成的数据文件往往带它。判断方法很简单如果答案总是比预期短一点、或者莫名奇妙地多出一个字符参与了匹配八成就是它在捣乱。还有一个隐蔽的坑如果你的程序先cin n读了长度紧接着getline读字符串那么getline会先读到cin留下的那个换行符拿到一个空串。解决办法是cin n之后加一句cin.ignore()或者干脆全用cin 。4.2 转移写错导致的典型错误我在带人做这题时见过几类高频错误列出来方便你对照第一种把dp[i][j] dp[i-1][j-1] 1写成了dp[i][j] dp[i][j] 1或者dp[i-1][j] 1。前者等于什么都没做后者会在字符不等时误加分。判断方法是用两个短序列手推一遍比如aab,bba正确答案是 1写错了会得到 2。第二种else 分支只取了dp[i-1][j]忘了dp[i][j-1]。这种错误在小数据上往往能蒙混过去因为dp[i-1][j]通常也不小。但如果 b 序列前几个字符很长一段都在 a 里找不到答案就会偏小。第三种忘了初始化。vector默认构造为 0这是对的但如果你用全局数组int dp[1005][1005];全局变量刚好也是默认清零的看起来没问题可要是你在多组测试数据里重复使用同一个数组而不重新清零上一组的残留值就会污染这一组这种错误最难查——单组测试明明是对的。养成习惯多组数据时在每组开头memset(dp, 0, sizeof(dp))。4.3 常见问题速查表我把排查经验整理成一张表遇到问题先按这张表对号入座能省掉大量瞎找的时间现象大概率原因处理方式样例能过提交大面积 WA输入格式读错比如序列带空格被cin截断改用getline并去掉行尾\r答案总比正确值小 1循环下标从 0 开始dp[i-1]越界或读到了错误边界统一 i、j 从 1 到 n/m取字符时用a[i-1]大数据 RE数组开小了没给结束符或 1-based 下标留位置容量至少开n 5大数据 MLE二维int表太大n、m 都在几千量级改用一维滚动数组或用位压缩存方向滚动数组版答案错乱diag备份时序写反用了本行新值当上一行旧值顺序固定为备份up、计算、更新diag输出方案时序列反了回溯是从右下角往左上角走的最后加reverse多组数据只有第一组对没清空 dp 数组每组开头 memset或用局部vector记忆化版本跑得跟暴力一样慢memo用 0 初始化把合法值 0 当成了未访问用 -1 初始化4.4 对拍与调试小数据暴力怎么写DP 写错最难的地方在于你盯着代码看不出问题但答案就是不对。这时候对拍是唯一靠谱的手段。暴力的写法很直接枚举 X 的所有子序列用一个二进制掩码从 0 到 2^n - 1按位决定保留还是删除对每个子序列判断它是不是 Y 的子序列在 Y 里从头扫一遍逐个匹配即可维护最大长度。n 取 8 到 12 就够用。然后再写个随机数据生成器随机生成长度 1 到 10、字符集只有三四个字母的序列。循环跑几百组把暴力和你的 DP 输出对比一旦不一致就把这组数据单独存下来。用三四个字母而不是 26 个是为了让随机数据里出现“相等字符”的概率变高更容易撞出分支覆盖不全的 bug。这个技巧我觉得特别值很多人随机数据用全字母表结果几百组跑下来一个 bug 都没暴露白白浪费了时间。另外把 dp 表完整打印出来跟手算的表对齐也是极好的调试手段小数据下用一次就够定位问题。5. 这道题还能延伸出什么5.1 最长公共子串把 dp 的含义换掉要求改成“公共子串必须连续”之后状态的含义必须跟着换dp[i][j]表示“以a[i-1]结尾、以b[j-1]结尾的公共子串的最大长度”。转移变得非常干净if (a[i - 1] b[j - 1]) dp[i][j] dp[i - 1][j - 1] 1; else dp[i][j] 0; // 断了就归零不能继承答案不再是dp[n][m]而是整张表里的最大值因为最长的那一段可能结束在任意位置。对比一下就能看出两种状态定义的差别一个记录“前缀范围内的最优”可以继承历史一个记录“必须卡在当前位置结尾”断了就得重来。把这两套模板分别写熟遇到变式题基本不会慌。5.2 两个排列的 LCS转成 LIS 做到 O(n log n)如果题目里的两个序列都是 1 到 n 的排列每个数恰好出现一次那 LCS 有更快的做法。原理是把 a 里每个数映射成它在 a 中的位置然后用这个映射去替换 b 里的每个数得到一个位置序列 P。b 的一个子序列如果和 a 的子序列公共那 P 上对应的这一段必须是递增的——因为它要在 a 里保持同样的先后顺序。于是问题变成了求 P 的最长上升子序列用贪心 二分可以做到O(n log n)。这个转换我第一次见的时候觉得相当漂亮。它提醒我一件事DP 的O(nm)是通用解但一旦题目附加了额外条件比如“排列”这种强约束往往存在更快的专用解法。做题时先看数据范围的量级n 到 1e5 还要求 LCS那就别想着二维表了赶紧往 LIS 方向想。5.3 和编辑距离的关系编辑距离Levenshtein Distance里如果只允许插入和删除、不允许替换那么两个字符串的距离正好等于n m - 2 × LCS。直觉是这样的先删掉两个串里所有不在公共子序列中的字符剩下的就是那 LCS再把它们补齐成对方总的操作次数就是两边各自删掉的字符数之和。这个关系在做文本相似度、版本差异对比之类的场景里很实用。不过要小心一旦允许“替换”操作编辑距离的转移就变成三路取最小了跟 LCS 的转移只差一点点但不能再套上面那个公式。写代码之前先确认清楚题目允许哪些操作这一步能避免大量返工。最后分享一个我自己做题的小习惯每道 DP 题只要条件允许我都会先用纸把状态含义和转移方程各写一行再动手写代码。LCS 这道题状态那一行就是“两个前缀的最长公共子序列长度”转移那一行就是“相等则左上加一不等则上下取大”。这两行写清楚了剩下的都是体力活。真正容易出错的地方从来不是敲代码而是状态定义偏了一点点导致后面所有推导都跟着歪。