3.8 最长公共子序列算法

这一篇讲动态规划在字符串上的经典应用——最长公共子序列（Longest Common Subsequence，LCS）。它是生物信息学（DNA 序列比对）、版本控制（diff）、拼写纠错的基础。它还确立了一个极常用的 DP 模式：双序列 DP（状态用两个序列的下标 $i,j$ 刻画）。

1.问题：两个序列最长的共同子序列

给两个序列 $X=x_1\cdots x_m$ 和 $Y=y_1\cdots y_n$ ，找它们最长的公共子序列。子序列不要求连续（区别于子串），只要求相对顺序一致。

比如 $X=\text{ABCBDAB}$ 、 $Y=\text{BDCAB}$ ，一个 LCS 是 $\text{BCAB}$ （长度 4）。

朴素枚举： $X$ 有 $2^m$ 个子序列，对每个检查是否为 $Y$ 的子序列——爆炸。但子问题高度重叠，DP 出场。

3.填表与还原

填 $(m+1)\times(n+1)$ 的表， $c[i,j]$ 依赖左、上、左上，所以从左到右、从上到下填。时间空间各 $O(mn)$ 。

要还原具体是哪个子序列（而不只是长度），填表时记一张决策表：每个格记"这个值来自左上(+1)、左、还是上"，最后从 $c[m,n]$ 回溯到 $c[0,0]$ 即可还原一条 LCS。

值得想清楚 $x_i\ne y_j$ 时为什么取 $\max(c[i-1,j], c[i,j-1])$ 。直觉： $x_i$ 和 $y_j$ 至少有一个不在 LCS 里（因为它俩不同，不可能同时在末尾）。如果 $x_i$ 不在，问题退化成 $X$ 前 $i-1$ 个 vs $Y$ 前 $j$ 个（即 $c[i-1,j]$ ）；如果 $y_j$ 不在，退化成 $c[i,j-1]$ 。两者取大即可。关键是"末尾字符是否匹配"决定了最优子结构怎么切分——匹配则共享末尾、不匹配则丢掉其一。

5.双序列 DP 的普适模式

LCS 确立了双序列 DP这个模式：状态 $f(i,j)$ 是"两个序列各看前 $i$ 、前 $j$ 个"，转移看末尾字符的关系。很多问题复用它：

编辑距离（Levenshtein）：把 $X$ 变成 $Y$ 最少要几次插入/删除/替换。转移更复杂（三种操作取最小），但状态结构同 LCS。
最长公共子串（要求连续）：转移在失配时清零而非取 max。
序列比对（带打分）：生物信息学里 DNA/蛋白质比对，是 LCS 的加权推广。

识别出"两个序列、状态用各自下标"这个特征，就往双序列 DP 靠。它是 DP 三大典型结构之一（线性、区间、双序列）。

6.练习

Q1. $X=\text{ABCBDAB}$ 、 $Y=\text{BDCAB}$ ，简述 $c[i,j]$ 表怎么填出 LCS 长度 4。

按 $x_i=y_j$ 则 $c[i-1,j-1]+1$ 、否则 $\max(c[i-1,j],c[i,j-1])$ 填。每当末尾字符匹配（如两个 B、两个 A、两个 B），LCS 长度沿对角线 +1。最终 $c[7,5]=4$ 。回溯决策表得一条 LCS 如 BCAB 或 BDAB。

Q2. LCS 转移里， $x_i\ne y_j$ 时为什么取 $\max(c[i-1,j], c[i,j-1])$ 而不是别的？

因为 $x_i\ne y_j$ ，它俩不可能同时在 LCS 末尾，至少一个不在。若 $x_i$ 不在，最优就是 $X$ 前 $i-1$ vs $Y$ 前 $j$ 的 LCS，即 $c[i-1,j]$ ；若 $y_j$ 不在，是 $c[i,j-1]$ 。两者涵盖所有可能，取较大。关键：末尾是否匹配决定子结构切分——匹配共享末尾，失配丢掉其一。

Q3.（思考题） LCS 是"双序列 DP"的代表。这个模式还能解什么问题？状态结构有什么共同点？

双序列 DP 状态都是 $f(i,j)$ = 两个序列各看前 $i$ 、前 $j$ 的最优。共同点：转移都看两序列末尾字符的关系（匹配/失配），据此决定共享末尾还是丢其一。编辑距离、序列比对、最长公共子串都复用这个骨架，只是转移里"操作"不同（LCS 是+1/max，编辑距离是 min+代价）。识别"两序列+末尾字符关系"就往双序列 DP 靠。

7.小结

最长公共子序列用双序列 DP，状态 $c[i,j]$ 看两序列前缀，转移由末尾字符匹配与否决定， $O(mn)$ 求解并可回溯还原。它确立了"双序列 DP"模式（编辑距离、序列比对都复用）。下一篇是第三卷的收尾，也是 DP 的极限挑战——指数级的 Held-Karp 旅行商。