最长公共子序列
最长公共子序列（LCS）寻找两个序列中都出现、相对顺序相同的最长序列，允许匹配位置之间有间隔。这类对齐可作为代码 diff 的基础：公共部分形成稳定骨架，其余内容再以增删等方式处理。
像两人回忆同一次旅行，细节不同，但部分事件顺序一致。LCS 可以跳过细节，不能重排留下的事件。
LCS 如何工作
长度 m 的序列有 2^m 种位置选择，包括空子序列；重复字符可能让不同位置选择产生相同内容。逐一生成并检查它是否在 b 中，成本指数增长。DP 复用前缀比较结果。
dp[i][j] 表示 a[:i] 与 b[:j] 的 LCS 长度。第 0 行和第 0 列代表空前缀，均为 0。
末尾字符相同，即 a[i - 1] == b[j - 1] 时：
dp[i][j] = dp[i - 1][j - 1] + 1
匹配字符延长排除当前两个位置后的解，所以读取左上角。不能从上方或左方加一，否则可能重复使用当前位置。
字符不同时，放弃 a 或 b 的一个末尾位置，取较长者：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
平局表示两种缩短前缀都能保留最优长度。本课优先向上，只为结果与播放确定，不代表 LCS 唯一。
右下角给长度，字符还需回溯：匹配时沿对角并输出字符，不匹配时移到能保持当前长度的邻居。
为什么最早匹配贪心会更短
对 a = ABCBDAB、b = BDCABA，从左扫描 a 并选择 b 中最早可用匹配，看似合理。第一步却把 a[0] = A 匹配到 b[3]，越过 b[0..2] = B, D, C，以后不能再用这些位置。
接着匹配 b[4] 的 B、b[5] 的 A，得到长度 3 的 ABA。它是合法公共子序列，但不是最长。
DP 保留上方和左方状态代表的选择，最终可恢复 BCBA：使用 b 的索引 0、2、4、5，长度 4。局部最早的一次匹配可能封死更好的整体对齐。
逐步演示
默认比较 ABCBDAB 与 BDCABA。
- 贪心先将
a[0]的 A 匹配b[3]。被划掉的 B、D、C 表示这些前缀位置已不可用。 - 再把
a[1]的 B 配到b[4]，a[5]的 A 配到b[5]，得到ABA、长度 3，保留作对照。 - DP 第 0 行、列置 0，表示与空前缀比较的完整答案。
- 按行从左到右填表。A 与 B、D、C 的前三格候选都为 0，直接写 0。
dp[1][4]的 A 与 A 匹配，左上 0 加一得 1；dp[2][1]的 B 与 B 也得 1。 - 不匹配时选择上或左的较大值。
dp[3][5]两邻居都为 2，本课按平局规则记向上。 - 最终
dp[7][6] = 4，旁边出现四个空结果位。只知道长度，还不知道字符。 - 从
(7, 6)回溯，B 与 A 不同，上方保留 4，所以到(6, 6)。A 匹配，把 A 放在最右结果位，再到(5, 5)。 - 从
(5, 5)向上到(4, 5)，B 匹配；对角后从(3, 4)向左到(3, 3)，C 匹配。 - 再对角到
(2, 2)，向左到(2, 1)，B 匹配，填入第一个位置。正序读出BCBA、长度 4。
其他合法平局规则可得到 BDAB，同样长度 4。表证明最优长度，回溯路径提供一个达到该长度的实例。
时间与空间复杂度
| 项目 | 成本 |
|---|---|
| 枚举 a 的子序列并在 b 中检查 | O(2^m × n) 的检查成本 |
| DP 填表 | O(m × n) |
| 完整表空间 | O(m × n) |
| 回溯 | O(m + n) |
m、n 是两序列长度。枚举项假设每个候选在 b 中用 O(n) 检查，实际生成候选也有开销。只求长度可压缩为两行，或谨慎原地更新的一行，用 O(min(m, n)) 空间。恢复字符需要更多信息，本课保留完整表。
边界情况
- 任一序列为空，LCS 为空，长度 0。
- 没有公共字符，所有格为 0，回溯不输出。
- 重复字符可能产生多条最优路径，固定平局只让输出可复现。
- 两序列相同，完整序列就是 LCS。
- 子序列允许间隔，不能当成要求连续的子串问题。
常见错误
- 匹配时用
max(top, left) + 1。 必须扩展左上状态。 - 不匹配也加一。 没有新增公共字符。
- 把早期全零平局当复杂决策。 两候选都是 0，记录 0 后继续即可。
- 缺少空前缀行列。 会让边界依赖失去基础。
- 依赖未完成就填格。 上、左、左上必须先有值。
- 认为最早匹配总安全。 默认首个 A 配到 b[3] 会失去支持
BCBA的前缀。 - 声称恢复序列唯一。 最优长度确定，但实现该长度的序列可能多个。