刷到最长公共子序列这道题的人大致分两种一种是刚学完背包、还没建立起二维状态直觉的新手看到两串字符就本能地想去逐位比对另一种是隔了很久回来复习老题的老手发现当年背下来的转移方程已经记不全了。信息学奥赛一本通 1265 这道【例9.9】最长公共子序列恰好卡在这两类人中间——它的代码短到只有十几行但每一行背后都藏着一个必须想明白的决策。我第一次做它的时候写出来的程序在小数据上跑得挺欢一交上去却只过了一半测试点后来花了整整一个晚自习才把问题揪出来那次的教训直到现在还在影响我写动态规划的习惯。这篇文章我打算把这道题彻底讲透从子序列和子串这两个听起来差不多、解法却天差地别的概念讲起把状态定义和转移方程一步步推出来再用一个真实的两行样例把整张 DP 表手工填一遍然后给出二维数组、滚动数组、记忆化搜索三种写法以及它们各自的坑最后聊怎么把具体的那条最长公共子序列打印出来以及这道题能延伸出的若干变式。不管你是完全没接触过动态规划还是只想找一份能直接抄的可靠代码应该都能从里面拿到点东西。1. 先分清子序列和子串一字之差决定了两种完全不同的解法1.1 子序列的定义到底宽在哪题目原文里对子序列的描述是在原序列中删去若干元素后得到的序列这句话里的关键词是删去若干元素注意它没有说必须删连续的、也没说不能跳着删。也就是说从字符串ABCBDAB里我可以保留第 1、2、4、6 位把它变成ABCB中间的D和最后的D、B被删掉了剩下的字符仍然保持原来的先后顺序——这就是一个合法的子序列。把它和子串放一起对比差距立刻就出来了。子串要求原串中一段连续的区域比如ABCBDAB的子串只能是ABC、CBD、BDAB这类连成一片的片段而子序列允许你挑挑拣拣只要不改变相对顺序中间隔多远都行。正因为多了这份自由度两个字符串的公共子序列数量会非常庞大短的两行字符串就可能藏着成千上万条穷举根本不可行。这个自由度还带来一个很反直觉的结论公共子序列的长度上限等于两个串中较短的那个的长度但通常达不到。因为每选一个字符你实际上是在两个串里各消耗掉一个位置而且这两个位置还必须匹配。我在给学生讲的时候喜欢用一个比喻把两个字符串想象成两条排队买票的队伍你要从两条队里各挑出若干人让他们按照同样的顺序举手人数最多能凑多少。你能跳着挑人但不能改变队里前后的站位关系。1.2 为什么子串的解法完全不能照搬新手最常见的错误就是拿求最长公共子串的思路来处理这道题。求最长公共子串有个很顺的写法令f[i][j]表示以第一个串第i位、第二个串第j位结尾的最长公共子串长度如果这两位字符相同就f[i][j] f[i-1][j-1] 1否则直接清零。这套状态之所以能这么简单是因为必须接连着这个限制把问题的结构切得很干净——一旦中断之前的积累就作废了。但 LCS 不行。假如你也用以某两位结尾来定义状态那么当这两位字符不同时你没法直接清零因为它们之前的匹配结果仍然是有效的可以继续往下接。这就说明**结尾这个锚点对子序列没有意义**你必须换一个能容纳已经匹配了多少且不管结尾在哪的状态。这个思路的转变才是这道题真正的门槛所在很多同学卡在这里不是因为不会写代码而是因为脑子里还残留着子串那套模型的惯性。我在实际带人的过程中发现判断一个人有没有真正理解这个区别只要问一个问题就够了两个字符串完全不相邻的两个相同字符能不能构成公共子序列的一部分能答当然能的人通常已经过了这一关。1.3 为什么它是理解动态规划的绝佳样板动态规划最难的部分从来不是写转移方程而是定义状态并证明最优子结构成立。LCS 恰好把这部分暴露得干干净净同时又不需要任何数据结构支撑连数组都不用开得多大。它的三个要素都特别清晰状态是一个二维的表格转移是三种情况取最大值没有后效性因为填表顺序天然保证前面的格子已经算完。如果你正在准备信息学奥赛的初赛或复赛LCS 是值得反复手推的题目。把手填表格的过程练熟比背下来一段代码有用得多。也正因如此课本把它放在例9.9这个位置前面几道例题大概率在打基础这道题是用来建立二维 DP 状态这个核心直觉的。理解它之后最长上升子序列、编辑距离、背包这些题的表格你会觉得长得越来越像。2. 状态设计与转移方程每一步的为什么都要说清楚2.1 f[i][j] 到底表示什么正式定义设两个字符串分别为s1和s2下标从 1 开始。令f[i][j]表示s1的前i个字符与s2的前j个字符所能构成的最长公共子序列的长度。这个定义有两个地方必须咬住不能松口。第一是前i个字符这个说法它意味着我们考虑的是一个前缀而不是整个串也不是以第i位结尾的某个东西。用前缀定义的好处在于答案最终就藏在f[n][m]这个格子里n、m分别是两串长度不需要再遍历一遍表格找最大值。很多同学写完发现最后还得在最后一行里扫一遍最大值八成就是把状态定义成以某位结尾了。第二是长度而不是序列本身。先求长度是标准做法因为长度这个数值有最优子结构可以直接参与比较和取最大而序列本身没法直接做加法比较得靠回溯来还原。这一点在后面的打印方案章节会详细展开。2.2 从分类讨论推出三选一的转移有了状态接下来问f[i][j]的值从哪来答案藏在s1的第i个字符和s2的第j个字符的比较里。情况一两个字符相等即s1[i] s2[j]。那么这两个字符可以一起被选进公共子序列的末尾而且这样做一定最优——因为它们是当前两个前缀的最后一个字符把它们配对不会有任何损失。于是f[i][j] f[i-1][j-1] 1。这里有个很多人会怀疑的点为什么不考虑即使相等也不选它们的可能性可以用反证法想一下。假设最优解没有用这一对相同的字符那么我们把这一对接到某个公共子序列的后面长度至少不会变短而且因为这两个字符分别在各自前缀的最后位置接上去也不会破坏顺序。所以选它们必然不亏。情况二两个字符不相等即s1[i] ! s2[j]。这时候这一对没法配对只能寄希望于之前的结果。而之前有两种可能要么抛弃s1的第i位看f[i-1][j]要么抛弃s2的第j位看f[i][j-1]。两者取最大即可f[i][j] max(f[i-1][j], f[i][j-1])。综合起来转移方程就是if (s1[i] s2[j]) f[i][j] f[i-1][j-1] 1; else f[i][j] max(f[i-1][j], f[i][j-1]);我自己习惯在草稿纸上把它写成一句更紧凑的话方便记忆相同则斜着加一不同则取上左的较大者。斜着指的是左上角f[i-1][j-1]上左指的是上方f[i-1][j]和左方f[i][j-1]。这个口诀在我做过的所有 LCS 变式里都管用。2.3 边界条件与初始化的细节边界其实非常自然只要有一个前缀是空的公共子序列长度当然是 0。所以f[0][j] 0j从 0 到mf[i][0] 0i从 0 到n。为了省事一般把字符串也按 1 下标存也就是s1从下标 1 开始算长度n的串。这样写出来的循环就是for (int i 1; i n; i)跟数学公式完全对齐不容易乱。至于第 0 行第 0 列的清零在 C 里用全局数组天然就是 0用局部数组的话写个memset或者干脆把数组开在main外面都能免掉一层初始化。提醒一点如果字符串长度能到 1000 以上f[1005][1005]这种int数组会占大约 4MB全局区一般放得下但如果长度到 10000就得考虑滚动数组了这块在第四章会讲。这道题一本通上的数据规模是字符串长度不超过 1000二维数组完全够用不需要提前优化。3. 手工填一遍表用两行真实样例把过程走完3.1 样例数据与表格布局一本通 1265 给我的样例输入是这样的两行abcicba abdkscab答案输出是4。我一开始看这个答案有点懵因为两个串的字符集合并不完全一样s1有is2有d、k、s能凑出长度为 4 的公共子序列吗后来手推了一遍才发现确实可以比如abcb就是一条合法解abca也是。这就说明一个问题公共子序列里的字符只要两串都有并且顺序一致就行中间夹着的不相关字符直接跳过。我们按 1 下标来s1 a b c i c b a长度 7s2 a b d k s c a b长度 8。表格行i从 0 到 7列j从 0 到 8。i\j01(a)2(b)3(d)4(k)5(s)6(c)7(a)8(b)00000000001(a)0111111112(b)0122222223(c)0122223334(i)0122223335(c)0122223336(b)0122223347(a)012222344右下角f[7][8] 4跟样例输出对上了。3.2 逐格推导观察数值变化的规律我挑几个关键格子说说它是怎么来的。先看f[1][1]s1[1]as2[1]a相等所以f[1][1] f[0][0] 1 1。这一行剩下的格子都等于 1因为s1只有一个as2里除了第 7 位还有a但那时左边的值已经是 1 了取最大还是 1。再看f[2][2]s1[2]bs2[2]b相等所以f[2][2] f[1][1] 1 2。这就是ab与ab的公共子序列长度显然对。值得盯一下的是f[3][6]s1[3]cs2[6]c相等所以f[3][6] f[2][5] 1。查表f[2][5] 2于是得到 3。这一格是斜着加一最典型的体现前面的 2 来自ab对ab加上这个配对的c就成了abc。最后看f[6][8]和f[7][7]这两个 4。f[6][8]s1[6]bs2[8]b相等f[6][8] f[5][7] 1 3 1 4。f[7][7]s1[7]as2[7]a相等f[7][7] f[6][6] 1 3 1 4。两条不同的路径各自凑出了长度 4这也解释了为什么这道题的答案不唯一。3.3 从填表顺序推断循环该怎么写填表的时候有个顺序约束必须遵守算f[i][j]要用到f[i-1][j-1]、f[i-1][j]、f[i][j-1]这三个格子在二维表格上分别位于左上、正上、正左。只要外层循环从小到大遍历i、内层循环从小到大遍历j这三个位置就都已经算好了。这就对应了最标准的双重循环写法for (int i 1; i n; i) for (int j 1; j m; j) // 转移我需要特别强调一遍这个顺序是必须而不是习惯。如果你把内层循环倒着写或者先遍历j再遍历i在某些写法下还能跑对但只要一上滚动数组优化就会立刻出错因为依赖关系被破坏了。养成从二维角度想清楚依赖的习惯比记住要正着写重要得多。4. 三种代码写法的取舍二维、滚动数组、记忆化搜索4.1 二维数组版最稳、最好调试这是我最推荐的入门写法也是考试时最不容易出错的一版#include iostream #include string #include algorithm using namespace std; const int MAXN 1005; int f[MAXN][MAXN]; int main() { string s1, s2; cin s1 s2; int n s1.size(), m s2.size(); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1[i - 1] s2[j - 1]) f[i][j] f[i - 1][j - 1] 1; else f[i][j] max(f[i - 1][j], f[i][j - 1]); } } cout f[n][m] endl; return 0; }注意这里s1用的是 0 下标字符串所以在访问的时候要写s1[i-1]而 DP 数组用的是 1 下标。这个字符串 0 下标、DP 数组 1 下标的错位是初学者最容易搞混的地方我见过太多人写成s1[i]然后越界或者错位比较结果样例过不了。它稳在哪f数组整张表都还在出问题的时候可以直接把表打印出来跟手推的结果对拍一眼就能看出哪一格算错了。调试价值极高。4.2 滚动数组版省内存但最容易写错方向当字符串长度上万的时候二维int数组会撑到几百 MB交上去直接超内存。这时可以用滚动数组把空间压到O(m)。核心观察是算f[i][j]只用到上一行f[i-1][*]和当前行f[i][j-1]也就是说任何时刻只需要保留两行。int f[2][MAXN]; for (int i 1; i n; i) { int cur i 1, pre (i - 1) 1; for (int j 1; j m; j) { if (s1[i - 1] s2[j - 1]) f[cur][j] f[pre][j - 1] 1; else f[cur][j] max(f[pre][j], f[cur][j - 1]); } } cout f[n 1][m] endl;或者更极限一点用一维数组原地滚动int f[MAXN] {0}; for (int i 1; i n; i) { int pre 0; // 保存 f[i-1][j-1] for (int j 1; j m; j) { int tmp f[j]; if (s1[i - 1] s2[j - 1]) f[j] pre 1; else f[j] max(f[j], f[j - 1]); pre tmp; } } cout f[m] endl;这段一维版本是最容易写错的f[j]在被覆盖之前代表的是上一行的值覆盖之后就变成当前行的值而f[j-1]在j正序遍历时已经是当前行的新值——正好对应转移里的max(f[i-1][j], f[i][j-1])。如果你把内层循环写成倒序f[j-1]就变成旧值了语义完全错位。一个自查手法用样例跑一遍滚动版本如果结果比二维版小八成是内层方向写反了如果结果偏大检查一下pre有没有在更新f[j]之后才被赋值。4.3 记忆化搜索最贴近人类直觉的写法如果你对两重循环填表的顺序总是不放心可以改用记忆化搜索。它的状态定义和二维 DP 完全一样但表达方式是我要算f(i, j)先去算它依赖的三个子问题int memo[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dfs(int i, int j) { if (i 0 || j 0) return 0; if (vis[i][j]) return memo[i][j]; vis[i][j] true; if (s1[i - 1] s2[j - 1]) memo[i][j] dfs(i - 1, j - 1) 1; else memo[i][j] max(dfs(i - 1, j), dfs(i, j - 1)); return memo[i][j]; }它的好处是不用操心循环顺序递归天然帮你把依赖关系理清楚了。代价是常数大一些而且递归深度可能到上千层某些评测环境栈空间不够会爆栈。在考场上我的建议是能用循环就用循环记忆化搜索留给那些转移关系复杂、循环顺序不好确定的题。5. 只要长度还不够怎么把具体的那条 LCS 打印出来5.1 从右下角往回走还原出一条路径很多变式题会要求输出那条最长公共子序列本身而不是长度。做法是先按上面的方法把整张表填完然后从f[n][m]出发倒着走走的过程中把匹配到的字符收集起来最后翻转一下就是答案。规则很简单站在(i, j)这个格子如果s1[i] s2[j]那么这个字符属于答案把它记下来然后往左上角走到(i-1, j-1)否则比较上方f[i-1][j]和左方f[i][j-1]往大的那个方向走。一直走到i 0或j 0停止。string lcs; int i n, j m; while (i 0 j 0) { if (s1[i - 1] s2[j - 1]) { lcs.push_back(s1[i - 1]); i--; j--; } else if (f[i - 1][j] f[i][j - 1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); cout lcs endl;用我们的样例跑一遍从(7, 8)开始s1[6]b和s2[7]b相等吗注意这里s1[7-1]as2[8-1]b不相等比f[6][8]4和f[7][7]4相等代码里用了所以往上走。走到(6, 8)s1[5]b和s2[7]b相等记下b跳到(5, 7)……继续下去会得到b c b a翻转前是倒序的a b c b输出abcb。这跟前面手推的结论一致。5.2 存在多条解时怎么保证输出稳定这道题只说求长度所以随便输出哪条都行但如果题目要求字典序最小的最长公共子序列就不能随便走了。判定的关键在回溯时的分支选择上——遇到f[i-1][j]和f[i][j-1]相等的时候走哪个方向会导致最终序列的字典序不同。我的经验是先在正向 DP 里处理好相等时优先从哪来或者在回溯阶段收集所有可能的路径再排序。前者效率高但要想清楚后者实现简单但只适合串很短的情况。具体到字典序最小我通常的做法是回溯时先把两条路径都试一遍取字典序更小的那条然后用记忆化避免重复计算——虽然写起来麻烦但正确性很稳。5.3 字符串规模变大后的输出方式如果n、m到了一万f数组本身就要 400MB肯定放不下更别说回溯了。这时候一般不会要求输出具体序列只会要长度。如果你真的遇到了必须输出序列的大数据那基本只能靠滚动数组 Hirschberg 算法这类分治技巧把空间降到线性。这个算法有点绕我在竞赛里几乎没遇到过需要手写它的场合属于了解即可的层次。6. 我踩过的坑与调试手法从爆零到一次过的完整排查链6.1 下标从 0 开始还是从 1 开始是个必须统一的事我第一次写这道题代码长这样for (int i 0; i n; i) for (int j 0; j m; j) { if (s1[i] s2[j]) f[i][j] f[i - 1][j - 1] 1; // 当 i 或 j 为 0 时越界 else f[i][j] max(f[i - 1][j], f[i][j - 1]); }表面看挺对实际上当i为 0 或j为 0 的时候f[-1][*]直接越界读到了一片垃圾值小数据可能侥幸蒙对大数据就会莫名其妙地给出偏大的答案。排查这类问题的正确姿势是在本地开-fsanitizeaddress编译跑一遍样例越界会立刻报出来比肉眼看快得多。修法只有一个统一口径字符串按 1 下标处理或者访问时统一减 1DP 数组一律按 1 下标存从(1,1)开始填第 0 行第 0 列一律是 0循环从 1 开始。改完之后代码立刻干净了。6.2 输入里的隐藏字符比你想的多这道题的输入是两行字符串用cin s1 s2读就行。但我遇到过好几次样例能过、提交全红的情况最后发现是本地测试文件用 Windows 换行复制粘贴的时候带进了不可见字符导致s1的尾部多了一个\r字符串长度比预期多 1。这种情况在 Linux 评测机上可能表现为某一位比较永远不相等让你误以为转移方程写错了。我的做法是本地读完字符串后把长度打印出来跟肉眼数的对比一下。数字对不上就是输入出了问题这时候去改转移方程纯属浪费时间。如果要做更严格的输入处理可以用getline逐行读再手动去掉末尾空白。6.3 把 LCS 和最大公共子串、编辑距离写串了这三种题的转移长得有点像但有一个决定性的区别题目类型状态含义字符不同时的处理最长公共子序列前缀s1[1..i]与s2[1..j]的 LCS 长度max(f[i-1][j], f[i][j-1])最长公共子串以s1[i]、s2[j]结尾的公共子串长度直接置 0编辑距离把s1[1..i]变成s2[1..j]的最少操作数min(插入, 删除, 替换) 1拿这张表对照一下自己的代码一般三秒钟就能看出是不是串了。症状也很典型如果写了 LCS 却输出得特别小多半是用成了子串的清零写法如果输出偏大得不合理可能是边界没清干净把上一次循环的残留值加进来了。6.4 输出答案前多打一行表比什么都值这一条是我最想分享的经验。写完 DP 之后别急着提交先在样例上把整张f表打印出来看一眼。填表类的题目只要表对了答案就一定对表错了答案对了也是碰巧。我养成的习惯是把打印语句写在一个#ifdef DEBUG里交之前把宏关掉就行既不影响性能也不影响调试效率。7. 从这一题延伸出去几个值得顺手练掉的变式7.1 最长公共子串为什么用不上这套表前面在对比表里已经提过最长公共子串的状态是以某两位结尾所以它的转移在字符不同时直接归零最后答案要在整张表里取最大值而不是读右下角。理解这个差异之后你会发现两类问题的本质区别在于子串有连续这个强约束状态可以锚定在结尾子序列没有所以必须用前缀定义。这个观察在我后来做字符串相关的题时反复用到。7.2 三个及以上的串求 LCS维度会炸如果把题目改成求三个串的最长公共子序列状态就变成f[i][j][k]转移要枚举 7 种组合三个位置分别选或不选时间复杂度是O(nmk)乘常数。串数再往上加维度爆炸内存和时间都扛不住。这类题目一般会限制串数和长度或者本身有特殊结构。我在比赛里见过的三串版本通常长度都在 100 以内直接三维数组硬怼就能过。7.3 最短公共超序列把 LCS 反过来用有个很漂亮的结论两个字符串的最短公共超序列长度等于n m - LCS长度。直观理解是公共部分只需要写一遍非公共部分各写一遍所以总长度是两串长度之和减去被合并掉的那部分。这个结论在字符串压缩、差异比对这类场景里经常出现知道了之后能省不少推导功夫。7.4 什么时候该考虑用后缀自动机如果题目里的字符串长度到了十万甚至百万O(nm)的 LCS 就彻底不可行了这时候得换后缀自动机这类工具把复杂度降到接近线性。不过这套东西的理解成本比二维 DP 高一个量级而且大部分信息学奥赛的题目数据规模都控制在 DP 能接受的范围内。我的建议是先把 LCS 的二维写法练到能闭着眼睛写对再考虑往高阶工具上走——基础不牢的时候上高级算法只会让你连错误都排查不了。最后再分享一个我自己用了很多年的小技巧每次写完 LCS 这类填表题我都会拿两三个短字符串在纸上随手画一张表把右下角的答案跟程序输出对一遍。这个过程耗时不超过三分钟但能挡掉绝大多数因为下标、初始化、循环方向引起的低级错误。真正让你在考场上丢分的往往不是算法想不出来而是这些明明知道却总在细节上翻车的地方。