最长公共子序列

给定两个序列 $X=x_1\cdots x_m$ 与 $Y=y_1\cdots y_n$，最长公共子序列（LCS）是在二者中都按原顺序出现的最长序列。

1. 子序列不是子串

子序列可以跳过元素，但不能改变相对顺序。例如 ACE 是 ABCDE 的子序列，却不是连续子串。若把题目误当成最长公共子串，状态转移会完全不同。

2. 状态定义

令

$$dp[i][j]=LCS(X[1..i],Y[1..j])\text{ 的长度}.$$

只看两个前缀的最后一个字符：

• 若 $x_i=y_j$，可以把这个公共字符接到更短前缀的答案后；
• 若 $x_i\ne y_j$，任一公共子序列不可能同时使用这两个末尾字符，至少要舍弃一个。

因此

$$dp[i][j]= \begin{cases} 0,&i=0\text{ 或 }j=0,\\ dp[i-1][j-1]+1,&x_i=y_j,\\ \max\{dp[i-1][j],dp[i][j-1]\},&x_i\ne y_j. \end{cases}$$

3. 填表顺序与复杂度

每个格子依赖左、上、左上，按行或按列填表即可。状态数为 $mn$，每格 $O(1)$：

$$T=O(mn),\qquad S=O(mn).$$

4. 为什么相等时一定能配对

当 $x_i=y_j$ 时，两个前缀存在一个以该字符结尾的最优公共子序列。若某个最优解没用它，可以在不缩短长度的情况下调整末尾匹配。因此问题缩为两个都去掉末尾后的 LCS，再加 1。

不相等时，最优解至多使用其中一个末尾，所以比较删掉 $x_i$ 与删掉 $y_j$ 的两个子问题即可。

5. 回溯出具体序列

从 $(m,n)$ 逆向移动：

• 若 $x_i=y_j$，把该字符加入答案，走到 $(i-1,j-1)$；
• 否则走向 $dp$ 值更大的上方或左方；
• 若两者相等，说明可能有多个 LCS，任选一个方向只会得到其中一个。

收集到的字符顺序是反的，最后需要翻转。

6. 一个例子

对

X = ABCBDAB
Y = BDCABA

LCS 长度为 4，BCBA 和 BDAB 都是合法答案。这说明“LCS 的长度唯一”不代表“LCS 序列唯一”。

7. 空间压缩

若只求长度，第 $i$ 行只依赖第 $i-1$ 行，可用两行，把空间降为 $O(n)$。进一步原地更新一行时，要额外保存更新前的左上角值。

但压缩后通常无法直接按整张表回溯序列。若既要低空间又要恢复方案，可以使用 Hirschberg 算法，以 $O(mn)$ 时间和 $O(\min(m,n))$ 空间递归恢复。

8. LCS 与编辑问题

若只允许插入和删除，把 $X$ 变成 $Y$ 的最少操作数为

$$m+n-2\operatorname{LCS}(X,Y).$$

共同保留 LCS，其余字符从 $X$ 删除、再向其中插入 $Y$ 的剩余字符即可。允许替换且代价独立时，则应使用最小编辑距离的专门状态。