最长公共子序列（Longest Common Subsequence，LeetCode 1143，Medium）是二维字符串 DP 的双子星之一（另一颗是本库《编辑距离》）：给两个字符串，找它们共有的、保持相对顺序的最长子序列。它是 diff 工具（git diff 的思想内核）、版本比对、DNA 序列分析的底层模型——也是所有「两个字符串、一张二维表」类 DP 的入门钥匙。本篇讲清它的状态设计、转移、方案回溯，以及它与编辑距离的亲缘关系。
状态与转移：一张二维表的逻辑
状态：dp[i][j] = s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度。转移只看两串的「末字符」是否相等：相等（s1[i-1] == s2[j-1]）——这个字符必然可以进入公共子序列的末尾，dp[i][j] = dp[i-1][j-1] + 1；不等——末字符至少有一个不进子序列，dp[i][j] = max(dp[i-1][j], dp[i][j-1])（丢掉 s1 的末字符或丢掉 s2 的末字符，取更优）。边界：dp[0][*] = dp[*][0] = 0（空串与任何串的公共子序列为空）。答案 dp[m][n]。时间空间 O(m×n)。为什么「相等时不需要再 max」：一个初学者常见疑问是「相等时能不能不配对、继续丢字符」——可以证明配对不会更差（不配对的最优解不会超过配对的 dp[i-1][j-1]+1），所以直接 +1 是安全的；这个「相等即配对」的贪心正确性，是 LCS 转移最值得想明白的一点。
def longest_common_subsequence(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[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]
回溯构造方案：从表里「走」出子序列
长度只是第一步，工程上常需要构造出这个子序列本身（diff 工具的本质：从 LCS 表回溯出「保留哪些、删除哪些」）。方法：从 dp[m][n] 出发逆向行走——当前字符相等：它是 LCS 的一员，记录它，走向左上 (i-1, j-1)；不等：走向 dp[i-1][j] 与 dp[i][j-1] 中较大的那个方向；走到边界（i 或 j 为 0）结束，逆向收集的字符反序即 LCS。diff 工具的扩展就在这同一个回溯里：走向左上是「s1 删除了一个字符」、走向上方是「s2 新增了一个字符」、相等走左上是「保持」——把每一步的移动类型记录下来，就是一份编辑脚本。这就是为什么说 diff 的内核是 LCS：git 的行为，是这张二维表的回溯旅行。
亲缘关系：与编辑距离、以及一族变形
LCS 与本库《编辑距离》（LeetCode 72）是双子星：同样的状态定义（前 i vs 前 j）、同样的二维表、相似的方向——编辑距离在「字符不等」时考虑的是「替换/删除/插入」三种操作取最小，LCS 考虑的是「丢弃一侧」取最大——两者的转移是同一棵决策树的两种度量（LCS 的长度与编辑距离之间存在换算关系：当只允许增删不允许替换时，m + n - 2×LCS = 最短编辑距离）。变形家族也由这对双子星统领：最长公共子串（要求连续——相等时才转移，断即清零）、最短公共超序列（LCS 的补集构造）、两个数组的 LCS（整数版）、以及「至少需要删除多少个字符使两个字符串相等」（m + n - 2×LCS 的直接应用）。学完双子星，二维字符串 DP 的主干就通了——变形题都是「同一个框架 + 一点业务规则」。
回溯构造的完整演示：diff 视角的三种移动
把回溯构造在 ("abcde", "ace") 上完整走一遍，展示「编辑脚本」的产出。DP 表构造完成后，从 (5,3)（dp=3）逆向行走：位置 (5,3)：s1[4]='e' == s2[2]='e' → 'e' 是公共子序列成员，记录，走向 (4,2)。(4,2)：s1[3]='d' ≠ s2[1]='c' → 比较 dp[3][2] 与 dp[4][1]（都为 2，任选一个方向——平局方向的选择决定 diff 的输出风格，约定优先左上或优先上，输出会不同但长度相同）；走向 (3,2)。(3,2)：s1[2]='c' == s2[1]='c' → 记录 'c'，走向 (2,1)。(2,1)：s1[1]='b' ≠ s2[0]='a' → 走向较大方向（假设 (1,1)）。(1,1)：s1[0]='a' == s2[0]='a' → 记录 'a'，走向 (0,0)，结束。逆序合并："ace" ✓。把移动类型翻译成 diff 语义：相等走左上 = 「保持行」；不等时若走向 i-1 = 「s1 删除了字符」（diff 的减号行）；若走向 j-1 = 「s2 新增了字符」（加号行）——git diff 的每一行输出，就是这张表的每一次移动。平局方向的约定还解释了 diff 工具的一个日常现象：同一段修改，不同工具输出的删除/添加行的分组方式不同——它们都正确（LCS 长度相同），只是平局的选择策略不同。
LCS 的空间优化：两行滚动与「无法回溯」的代价
LCS 的二维表可以滚动到两行（转移只依赖上一行与本行左边）——prev、curr 两行交替，空间从 O(m×n) 压到 O(min(m,n))（短串做内层维度）。但空间优化的代价在这里特别沉重：滚动掉的是「回溯构造方案」的能力——diff 场景恰恰需要完整表来回溯编辑脚本！这是 DP 空间优化的一个通用张力：优化空间的技巧（滚动、压缩）几乎都以「放弃回溯」为代价——「只要长度」的场景放心滚动，「要方案」的场景保留全表（本库《编辑距离》的工程语境：只算相似度用滚动，要生成 diff 保留全表）。折中方案也存在：Hirschberg 算法用分治把空间压到 O(min(m,n)) 同时仍能构造方案（时间翻倍）——它是「空间优化与回溯兼得」的学术解，工程上较少使用但思路值得知道——分治 + 线性空间合并，是把「不可回溯」变成「可分治回溯」的漂亮手法。
LCS 的应用地图：diff、DNA、代码克隆
LCS 的应用远不止教科书，三个真实的产业场景值得认识。应用一：diff 与版本控制——git diff 的行级比对（本篇正文的回溯旅行），加权的变体（移动的代码块识别、重命名的检测——现代 diff 工具的智能启发都在 LCS 的扩展上）；应用二：DNA 序列比对——生物信息学的序列比对（BLAST 类工具的思想内核——两条基因链的最长公共子序列与相似度评分，是 LCS 带评分矩阵的加权版——本库《编辑距离》的评分矩阵同理）；应用三：代码抄袭检测——两个代码文件的 token 序列 LCS（token 化后比对——格式与变量名的差异被 token 化抹平，结构性抄袭无所遁形——学术诚信与代码审计的工具）。三个应用的共同技术底座：LCS 的「保持顺序的最大公共结构」——顺序敏感 + 容忍删除，这个组合恰好是「演化与修改」的数学模型——一切「同源但有改动」的序列比对，都是 LCS 的领地。
LCS 的滚动实现细节：两行交替的边界
LCS 的两行滚动实现有一个容易写错的细节：行的交替与取模。写法一：prev, curr = curr, new_row（每行构造新行）——清晰但每行都新建列表；写法二：dp[i % 2] 双数组复用（省去分配）——复用时的覆盖语义要精确：dp[i%2][j] 是「当前行」，dp[(i-1)%2][j] 是「上一行」，转移 max(dp[(i-1)%2][j], dp[i%2][j-1])——注意 dp[i%2][j-1] 是当前行已更新的左边（不是上一行！它在本行遍历时刚更新）——复用数组时「上一行的自己」会被当前行的更新覆盖，恰好不影响正确性（LCS 的转移只用上一行的 j 与本行的 j-1）——但「恰好不影响」不等于「永远不影响」：其他 DP 的转移若依赖「上一行的 j-1」，双数组复用就会踩雷（三个状态变量的转移需要三行滚动）。滚动数组的验证纪律：小规模 DP 表手画 → 滚动版跑同样输入 → 两表逐格比对——十分钟的比对，防住「覆盖语义」这类静默 bug**。
LCS 的「不连续性」编辑距离的亲缘再探
LCS 与编辑距离的统一视角值得进一步阐明。两者都是两个序列对齐的问题，只是允许的操作集不同。LCS 允许的操作是从两串各自删除字符使剩余部分相等（删除操作）——编辑距离允许删除、插入、替换（增删改三操作）——编辑距离的操作集包含 LCS 的操作集。这个统一视角的实用价值：学会其中一个，另一个就是换一组操作集的变体——状态定义不变、转移方程按操作集微调。编辑距离的三个转移对应 LCS 的两个转移——对应关系一目了然。字符串 DP 的所有变体，都是「对齐 + 操作集」这个母题的变奏。
LCS 与编辑距离的换算公式
LCS 与编辑距离之间存在一个精确的换算关系（当编辑距离只允许增删不允许替换时）：最短编辑距离 = m + n - 2 × LCS。直觉证明：m + n 是把两个串都清空再重建的总操作数，而 LCS 的每个字符可以免删免插（公共子序列的字符保留），节省的操作数是 2 × LCS。这个换算的实用价值：知道了 LCS，就知道了最短编辑距离（反之亦然）——两个问题在仅增删的操作集下完全等价。允许替换后的编辑距离的换算关系会更复杂，但底层的对齐框架不变——本库的编辑距离与这篇的 LCS 合起来，覆盖了序列对齐的全部基础操作。
小结
这篇收成四条：LCS 的状态 dp[i][j] = 两串前缀的公共子序列长度，相等则左上+1（相等即配对是安全的贪心）、不等则取左右上最大；回溯构造方案从右下角逆向行走，记录移动类型即得编辑脚本——diff 的内核就是这张表的回溯；LCS 与编辑距离是同一棵决策树的两种度量，m+n-2×LCS 是仅增删时的最短编辑距离；变形家族（公共子串、最短公共超序列、删除计数）共用同一框架，学完双子星即通二维字符串 DP 主干。
参考资料
- LeetCode 1143. Longest Common Subsequence —— 题目与官方题解
- 本库前篇：《LeetCode 72. 编辑距离》《LeetCode 300. 最长递增子序列》—— 二维与一维序列 DP 的双子星
- 经典教材（算法导论）LCS 章节 —— 回溯构造与 diff 关系的原始出处
读者留言
COMMENTS 暂无还没有留言，来说第一句？