企业官网建设流程全解析

刷到"最长公共子序列"这道题的人，大致分两种：一种是刚学完背包、还没建立起二维状态直觉的新手，看到两串字符就本能地想去逐位比对；另一种是隔了很久回来复习老题的老手，发现当年背下来的转移方程已经记不全了。信息学奥赛一本通 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] = 0（j从 0 到m），f[i][0] = 0（i从 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有i，s2有d、k、s），能凑出长度为 4 的公共子序列吗？后来手推了一遍才发现确实可以，比如abcb就是一条合法解，abca也是。这就说明一个问题：公共子序列里的字符，只要两串都有并且顺序一致就行，中间夹着的不相关字符直接跳过。

我们按 1 下标来，s1 = a b c i c b a（长度 7），s2 = a b d k s c a b（长度 8）。表格行i从 0 到 7，列j从 0 到 8。

右下角f[7][8] = 4，跟样例输出对上了。

3.2 逐格推导，观察数值变化的规律

我挑几个关键格子说说它是怎么来的。

先看f[1][1]：s1[1]='a'，s2[1]='a'，相等，所以f[1][1] = f[0][0] + 1 = 1。这一行剩下的格子都等于 1，因为s1只有一个a，s2里除了第 7 位还有a，但那时左边的值已经是 1 了，取最大还是 1。

再看f[2][2]：s1[2]='b'，s2[2]='b'，相等，所以f[2][2] = f[1][1] + 1 = 2。这就是ab与ab的公共子序列长度，显然对。

值得盯一下的是f[3][6]：s1[3]='c'，s2[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]='b'，s2[8]='b'，相等，f[6][8] = f[5][7] + 1 = 3 + 1 = 4。f[7][7]：s1[7]='a'，s2[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]='a'，s2[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][*]直接越界读到了一片垃圾值，小数据可能侥幸蒙对，大数据就会莫名其妙地给出偏大的答案。排查这类问题的正确姿势是：在本地开-fsanitize=address编译跑一遍样例，越界会立刻报出来，比肉眼看快得多。

修法只有一个，统一口径：字符串按 1 下标处理（或者访问时统一减 1），DP 数组一律按 1 下标存，从(1,1)开始填，第 0 行第 0 列一律是 0，循环从 1 开始。改完之后代码立刻干净了。

6.2 输入里的隐藏字符比你想的多

这道题的输入是两行字符串，用cin >> s1 >> s2读就行。但我遇到过好几次"样例能过、提交全红"的情况，最后发现是本地测试文件用 Windows 换行，复制粘贴的时候带进了不可见字符，导致s1的尾部多了一个\r，字符串长度比预期多 1。这种情况在 Linux 评测机上可能表现为某一位比较永远不相等，让你误以为转移方程写错了。

我的做法是：本地读完字符串后，把长度打印出来跟肉眼数的对比一下。数字对不上就是输入出了问题，这时候去改转移方程纯属浪费时间。如果要做更严格的输入处理，可以用getline逐行读再手动去掉末尾空白。

6.3 把 LCS 和最大公共子串、编辑距离写串了

这三种题的转移长得有点像，但有一个决定性的区别：

拿这张表对照一下自己的代码，一般三秒钟就能看出是不是串了。症状也很典型：如果写了 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 这类填表题，我都会拿两三个短字符串在纸上随手画一张表，把右下角的答案跟程序输出对一遍。这个过程耗时不超过三分钟，但能挡掉绝大多数因为下标、初始化、循环方向引起的低级错误。真正让你在考场上丢分的，往往不是算法想不出来，而是这些明明知道却总在细节上翻车的地方。