企业官网建设流程全解析

很多刚开始接触动态规划的人，都是在“最长公共子序列”这道题上卡了最久。我也一样，第一次看到编号 1143 时，觉得它名字又长又绕，题目描述就一句话：给定两个字符串，返回它们的最长公共子序列长度。但真正动手去推状态转移方程，才发现这一句话背后藏着二维动态规划几乎全部的核心套路——状态怎么定义、转移为什么分两路、表怎么填、表填完以后怎么把序列本身还原出来。

这篇文章我会把 LCS（Longest Common Subsequence，最长公共子序列）从零讲到能应付面试追问的程度：先辨析子串和子序列的区别，再手推一张完整的 DP 表，给出 C++ / Python / Java 三种实现，讲透滚动数组的空间优化，最后聊聊它在 diff 工具、基因序列比对、文本查重里的真实作用，以及我梳理出的常见踩坑点。无论你是刚入门的算法新手，还是想整理动态规划模板的求职者，都能按自己的节奏读完。

1. 认清题意的第一步：子序列不是子串，差一个连续就天差地别

1.1 三个最容易混淆的概念

题目里的“子序列”是很多新手摔跤的第一个地方。它和“子串”听起来像一回事，实际上完全不同。

• 子串（Substring）：必须连续。比如字符串 “abcde” 的子串有 “abc”、“cd”、“de”，但 “ace” 不是子串，因为中间缺了字符。
• 子数组（Subarray）：数组版本的子串，同样要求连续。
• 子序列（Subsequence）：不要求连续，只要求保持相对顺序。从 “abcde” 里挑出第 1、3、5 个字符，得到 “ace”，这就是一个合法子序列。

子序列不要求连续，这个特性让它比子串更难处理。子串可以用滑动窗口在线性时间内解决，子序列却天然带有“跳过某些字符”的自由度，暴力枚举的话，对于一个长度为 n 的字符串，可能出现的子序列数量是 2^n 个。题 1143 要求的是两个字符串的公共子序列中最长的那个的长度，这就是为什么需要用动态规划这种全局规划的思路，而不是贪心或者滑动窗口。

1.2 用一个小例子理解问题目标

假设有两个字符串：

• text1 = “abcde”
• text2 = “ace”

肉眼观察一下：两个字符串都包含字符 a、c、e，而且这三个字符在两边出现的位置都是从左到右依次排列的。所以 “ace” 是它们的公共子序列，长度是 3。还有没有更长的？“abc” 不是 text2 的子序列，因为 text2 里没有 b；“cde” 也不是 text2 的子序列，因为 text2 里 d、e 之间没有 c 和 d。所以答案是 3。

这个例子看起来简单，但它暴露了核心问题：两个字符串各自长度为 m 和 n 时，可能的子序列组合数量是 2^m × 2^n 级别，完全不可能枚举。必须找到一种方式，把答案拆成规模更小的子问题，逐步递推得到结果。

还需要注意边界情况：如果其中一个字符串为空，公共子序列只能是空串，答案是 0。这个边界条件在代码里必须处理好，后面讲 DP 表初始化时你会看到，垫一行和一列就是在处理这个边界。

2. 动态规划的状态从哪来：两个字符串递推的本质

2.1 暴力枚举为什么不可行

先替大家算一笔账。text1 长度是 1000，text2 长度是 1000 时，如果试图枚举 text1 的所有子序列，数量是 2^1000 量级，这个数字比可观测宇宙中的原子总数还大好几倍。显然暴力遍历走不通。

换个思路：求两个字符串的 LCS，本质是“逐步决策”——对于每个字符，是把它选进公共子序列，还是跳过它。这种决策过程天然适合动态规划，因为一旦某个位置之前的选择确定下来，之后的最优解就只依赖当前状态，而不依赖之前是怎么走到这一步的。

2.2 状态定义与转移方程的推导

定义二维数组 dp[i][j]，表示 text1 的前 i 个字符（即 text1[0..i-1]）和 text2 的前 j 个字符（即 text2[0..j-1]）的 LCS 长度。最终答案就是 dp[m][n]。

这个定义里最需要注意的是下标偏移。因为 i 表示长度而不是位置，text1 的第 i 个字符要写成 text1[i-1]，新手写代码时这里极其容易搞混。

转移关系分为两种情况：

1. 如果 text1[i-1] == text2[j-1]，说明这两个字符可以作为公共子序列的最后一个字符。它们可以直接接在 text1 前 i-1 个字符和 text2 前 j-1 个字符的 LCS 后面。所以：

   dp[i][j] = dp[i-1][j-1] + 1

2. 如果 text1[i-1] != text2[j-1]，说明当前这两个字符不能同时作为公共子序列的结尾。那么，dp[i][j] 要么是 text1 前 i-1 个字符和 text2 前 j 个字符的 LCS，要么是 text1 前 i 个字符和 text2 前 j-1 个字符的 LCS，取较大者。所以：

   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

这个方程是整道题的灵魂。它的含义可以这样理解：永远只比较两个字符串的尾部字符。相等就双双缩进一格；不相等就舍弃其中一边的尾部字符，看看哪边舍弃后更划算。

2.3 手推一遍完整 DP 表

光背公式不够，亲手填一次表才能真正理解。用 text1 = “abcde”，text2 = “ace” 为例。

初始化：dp[0][j] 和 dp[i][0] 都等于 0，因为任意字符串和空字符串的 LCS 都是 0。矩阵规模是 6 行 4 列。

逐行推演一下：

• i=1，text1 当前字符是 a。和 text2 的 a 相等时 dp[1][1] = dp[0][0] + 1 = 1；和 c 不相等时 dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1；和 e 不相等时同理等于 1。
• i=2，当前字符是 b。b 和 a、c、e 都不相等，所以这一行三个位置都是取“上方”和“左边”的较大值，全部是 1。你会发现 b 没有对结果产生任何贡献。
• i=3，当前字符是 c。c 和 c 相等，dp[3][2] = dp[2][1] + 1 = 2，其它位置继续取 max，都是 1 或 2。
• i=4，当前字符是 d。d 和谁都不匹配，整行只做 max 操作，值没有变化。
• i=5，当前字符是 e。e 和 e 相等，dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3。

看到没，不匹配的字符（比如 b 和 d）在表格里不会改变任何值，它们只是“路过”的，真正让表格前进的只有匹配字符。最终 dp[5][3] = 3，这就是答案。

提示：如果你现在正盯着这张表，可以仔细看 dp[3][2] = 2 这个格子。它是靠 dp[2][1] + 1 得到的，而 dp[2][1] 是处理完字符 a 之后的状态。这意味着表里每个格子都沉淀了前面所有字符的信息，这就是动态规划“用空间换时间”的精髓。

3. 三语言实现与空间压缩：从二维表到一行数组

3.1 标准二维 DP 实现

理解了转移方程，写代码就是机械工作了。我给出三种常用实现，逻辑完全一致。

// C++ 二维 DP 实现 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[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[m][n]; } };

# Python 二维 DP 实现 def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[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[m][n]

// Java 二维 DP 实现 class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }

这段代码的复杂度是时间 O(m×n)，空间 O(m×n)。当 m 和 n 都在 1000 量级时，二维数组大概有 10^6 个整数，内存约 4MB 左右，没有问题。

3.2 滚动数组：把空间压到一维

但如果字符串长度到 5000，二维数组就有 2500 万个格子，内存约 100MB；如果到 10000，就是 1 亿个格子，直接超过 400MB，很多环境就扛不住了。这时必须优化空间。

观察转移方程可以发现，计算 dp[i][j] 只用到三样东西：dp[i-1][j-1]（左上角）、dp[i-1][j]（上方）、dp[i][j-1]（左方）。也就是说，当前行只依赖上一行和当前行自身，再往上的行没有任何用处。所以我们只需要保存一行，逐行刷新。

// C++ 滚动数组实现 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<int> dp(n + 1, 0); for (int i = 1; i <= m; ++i) { int prev = 0; // 相当于 dp[i-1][j-1] for (int j = 1; j <= n; ++j) { int temp = dp[j]; // 更新前，dp[j] 仍是 dp[i-1][j] if (text1[i - 1] == text2[j - 1]) { dp[j] = prev + 1; } else { dp[j] = max(dp[j], dp[j - 1]); } prev = temp; // 下一轮循环中，这个 temp 就是新的 dp[i-1][j-1] } } return dp[n]; } };

# Python 滚动数组实现，可交换字符串进一步节省空间 def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) if m < n: # 让短串做列方向，空间进一步压缩 text1, text2 = text2, text1 m, n = n, m dp = [0] * (n + 1) for i in range(1, m + 1): prev = 0 for j in range(1, n + 1): temp = dp[j] if text1[i - 1] == text2[j - 1]: dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j - 1]) prev = temp return dp[n]

很多人在滚动数组这里写错，问题都出在 prev 和 temp 的顺序上。我建议在代码里把注释直接写上“更新前 dp[j] 是 dp[i-1][j]”，因为循环从左到右顺序更新数组，未被更新的 dp[j] 恰好就是上一行的同位置值；而 dp[j-1] 因为刚被更新过，恰好是当前行的左方值。prev 变量专门用来保住左上角的值，因为原来的 dp[j-1] 在上一轮已经被覆盖了。

3.3 为什么不用贪心或者双指针？

基于 LCS 的贪心算法在某些特殊情况下能拿正确答案，比如两个字符串结构高度一致时，但一旦遇到复杂交错情况就会出错。我见过 A 同学试图用“从两个字符串左端同时向右扫描，能匹配就匹配”的方式求解，在 “acdef” 和 “ace” 上勉强能过，换成 “abcde” 和 “acebde” 就直接错了。因为贪心只看眼前，无法做出跳过多余字符的全局决策。动态规划之所以是这类问题的标准解法，就是因为它把“选与不选”全部纳入状态，不漏掉任何一种可能性。

4. 不只要长度：回溯还原最长公共子序列本身

很多题目只问长度，但面试环节经常追加一句“能不能把那个子序列打印出来”。如果 DP 表还完整保存在二维数组里，回溯是很容易做到的。

4.1 从 DP 表反推路径的三个规则

从右下角 dp[m][n] 出发，向左上回溯：

1. 如果 text1[i-1] == text2[j-1]，说明这个字符被加入了 LCS，记录它，然后 i--、j--。
2. 如果不等，比较 dp[i-1][j] 和 dp[i][j-1]，哪个大就往哪个方向走。因为较大的值意味着当前位置的 LCS 长度是从那边继承来的。
3. 遇到 i == 0 或者 j == 0 时停止，因为已经回溯到空串边界。

注意：如果 dp[i-1][j] 和 dp[i][j-1] 相等，两条路都能走，这意味着 LCS 可能不唯一。回溯时选择不同方向会得到不同的合法答案。

def printLCS(text1: str, text2: str) -> str: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[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 = m, n while i > 0 and j > 0: if text1[i - 1] == text2[j - 1]: res.append(text1[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1 return ''.join(reversed(res))

4.2 多解时的行为差异

拿 text1 = “ABCBDAB”，text2 = “BDCABA” 举例，肉眼可辨的 LCS 有 “BCBA” 和 “BDAB” 等多种。回溯时，如果程序遇到 dp[i-1][j] == dp[i][j-1] 总是优先往上走，那么它会输出 “BCBA”；如果优先往左走，可能输出 “BDAB”。两者长度都是 4，都是正确答案。

如果题目要求“输出字典序最小的 LCS”，就不能简单回溯了。一个可行思路是倒着构造：把两个字符串反转，求反转后的 LCS，再从末尾开始按字典序选择字符。这个问题比较进阶，面试中出现的频率不高，但知道有这么回事总比当场傻眼好。

5. LCS 真的只是面试题吗？两个真实场景和一个进阶方向

5.1 diff 工具与版本控制的底层逻辑

日常开发里最常见的 LCS 应用就是 diff。比如你改了某个文件的几行，diff 工具需要判断哪些行是新加的、哪些行是删掉的、哪些行没变。这里把文件的每一行当作一个“字符”，对修改前后的文件序列求 LCS，那么LCS对应的行就是没变的部分，剩下的行就是增删部分。

版本控制里的 merge 和冲突标记，底层也在做类似的事情。两个分支分别修改了同一个文件，系统要找出两边共同保留的行，本质上就是在多个序列之间找公共部分。理解了 LCS，再去看 diff 输出就会明白，它为什么有时会把一段改动描述成“这里删了几行，那里加了几行”，而不是逐字对照——因为它先找到了最长未变序列，然后以它为锚点描述变化。

5.2 生物序列比对的入门视角

在生物信息学里，DNA 序列由四种碱基组成，可以看作一个只有四个字符的字符串。两条 DNA 序列比对的核心任务之一，就是找出它们的相似片段，判断哪些碱基是保守的、哪些是突变的。LCS 模型可以直接用于粗略的相似性判断：两条序列的 LCS 越长，保守片段越多，亲缘关系可能越近。

当然真实场景比这个复杂得多，会用到替换矩阵、空位罚分等机制，但如果你去读相关入门资料，会发现它们的目标函数里依然有 LCS 的影子。这也是为什么很多计算生物学课程会把 LCS 作为算法预修内容。

5.3 文本相似度计算与查重

两个文本中间接重复的部分，也可以通过 LCS 衡量。简单做法是：提取文本的关键行或者去停用词后的 token 序列，求 LCS 长度，再除以较短文本的长度得到相似度。比如一段代码和它的修改版之间，LCS 占比越高，说明复用的代码越多。这在检测作业抄袭、代码克隆时是很朴素但有效的特征。

公式表达：

• 相似度版本一：LCS 长度 / min(m, n)
• 相似度版本二：2 × LCS 长度 / (m + n)

第二个公式也叫 Dice 系数，它对长短不一的文本约束更严格，因为分母是两边长度和。工程上具体用哪个，取决于你更看重召回还是更看重误报。

5.4 从 LCS 延伸出去的一串经典问题

LCS 学完之后，可以顺藤摸瓜去看几个变种，它们是面试官最爱做的扩展：

1. 最短公共超序列（SCS）：将两个字符串合并成一个包含两者的最短字符串。长度公式是 m + n − LCS。若 text1 = “abcde”、text2 = “ace”，SCS 长度为 5 + 3 − 3 = 5，即 “abcde” 本身。
2. 编辑距离（莱文斯坦距离）：如果只允许插入和删除两种操作，把一个字符串变成另一个字符串的最小步数就是 m + n − 2 × LCS。如果还允许替换操作，就要用另一种 DP 模型。
3. 最长递增子序列（LIS）：可以用先排序去重、再求 LIS 与 LCS 的等价关系来理解，不过 LIS 有 O(n log n) 的专门解法，更高效。
4. 多序列 LCS：三个以上字符串求公共子序列是 NP-hard 问题，工程上只能用启发式近似。

每条分支都值得再深入一两天。等你把 SCS 和编辑距离都手推过一遍，回头再看 LCS，会发现自己对整个字符串 DP 家族都有了框架性认识。

6. 刷题踩坑记录与针对 1143 的常见误区

6.1 五个高频错误写法

我在排查同学代码的过程中，见过大量雷同的错误，整理成表格给大家参考：

下标偏移是最隐蔽的。因为 dp 表比原字符串多了一行一列，原字符串第 i 个字符一定是 text1[i-1]。我建议所有人在写循环时都先在注释里标注“i 是长度，不是下标”，能有效避免这个问题。

6.2 面试中被追问的几种变形

面试官很少满足于你默写一遍二维 DP，他们通常会连续追问：

• “长度很大，内存不够怎么办？”——滚动数组，同时把较短的字符串作为列方向，把空间降到 O(min(m, n))。
• “如果还要输出最长公共子序列本身呢？”——保留完整 DP 表并回溯；如果用滚动数组，需要额外记录选择路径。
• “如果两个字符串里有一个特别长呢？”——长到 O(m×n) 时间也无法接受时，要改用基于连续公共子串的近似方法，或者针对数据特征设计 bitset 加速。

这些追问其实都是同一个思路：你能不能在基础解法之上，分析清楚时间、空间瓶颈，并给出合理的 trade-off。LCS 是一道非常适合展示这种分析过程的题目。

6.3 我个人练习时的体会

最后说点平时刷题时很容易忽略的东西。我见过太多初学者能把转移方程背下来，但让 TA 在白板上画出 abcde 和 ace 的 DP 表，却画不出来。这其实是很危险的信号，因为 DP 题的核心不是背公式，而是理解表格里每一格是怎么来的、为什么这样来。

我的建议是：拿到任何一道 DP 题，先别急着写代码，拿一个不超过 5 个字符的小例子，在纸上把整个 DP 表从头到尾填一遍。填过三张表以后，你会自然形成一种直觉——看到“求两个序列的最值”，第一反应就是二维状态、双指针遍历、按尾部字符分类讨论。这种直觉才是刷题真正沉淀下来的东西。1143 这道题贵为入门必刷，也正是因为它能把这套范式完整地演示一遍。