最长公共子序列（LCS）

核心结论

最长公共子序列（Longest Common Subsequence，LCS）要求元素的相对顺序保持不变，但不要求它们在原序列中连续。

对长度分别为 m 和 n 的两个序列，经典动态规划算法的时间复杂度为 $\Theta(mn)$，空间复杂度为 $\Theta(mn)$。

1. 问题定义

给定两个序列：

$$X=\langle x_1,x_2,\ldots,x_m\rangle, \qquad Y=\langle y_1,y_2,\ldots,y_n\rangle$$

寻找一个最长序列：

$$Z=\langle z_1,z_2,\ldots,z_k\rangle$$

使得 Z 同时是 X 和 Y 的子序列。

1.1 子序列

若存在严格递增的下标序列：

$$1\le i_1<i_2<\cdots<i_k\le m$$

使得：

$$z_t=x_{i_t}, \qquad 1\le t\le k$$

则称 Z 是 X 的子序列。

例如，对于 X = ABCBDAB，BCBA 是 X 的子序列，可以依次选择：

B(2) → C(3) → B(4) → A(6)

子序列与子串

• 子序列只要求相对顺序一致，不要求连续。
• 子串要求字符在原字符串中连续出现。

2. 基本思想

LCS 具有动态规划的两个典型性质：

1. 最优子结构：原问题的最优解可以由规模更小的子问题最优解构成。
2. 重叠子问题：直接递归时，同一对前缀会被重复求解。

考虑两个前缀：

$$X[1\ldots i] \qquad\text{与}\qquad Y[1\ldots j]$$

比较它们的最后一个元素 $x_i$ 和 $y_j$。

2.1 当前元素相等

若 $x_i=y_j$，则该元素可以作为当前公共子序列的最后一个元素。

删除这个相同元素后，问题转化为两个更短前缀的 LCS：

$$c[i][j]=c[i-1][j-1]+1$$

2.2 当前元素不相等

若 $x_i\ne y_j$，则 $x_i$ 与 $y_j$ 不可能同时作为 LCS 的最后一个匹配元素，因此至少要舍弃其中一个：

• 舍弃 $x_i$，得到子问题 $c[i-1][j]$；
• 舍弃 $y_j$，得到子问题 $c[i][j-1]$。

应保留两种方案中的较优者：

$$c[i][j]=\max\{c[i-1][j],c[i][j-1]\}$$

3. 状态定义与递推关系

定义：

$$c[i][j] = \left| \operatorname{LCS} \bigl(X[1\ldots i],Y[1\ldots j]\bigr) \right|$$

即，$c[i][j]$ 表示 X 的前 i 个元素与 Y 的前 j 个元素的最长公共子序列长度。

3.1 边界条件

只要有一个前缀为空，公共子序列长度就是 0：

$$c[i][0]=0, \qquad c[0][j]=0$$

3.2 状态转移方程

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

记忆方式

• 当前元素相等：取左上角加 1。
• 当前元素不相等：取上方和左方的较大值。

4. 具体过程

考虑示例：

X = ABCBDAB
Y = BDCABA

其中 $m=7$，$n=6$。

4.1 初始化

创建一个大小为 $(m+1)\times(n+1)$ 的二维数组 c。

将第 0 行和第 0 列全部初始化为 0，因为空序列与任意序列的 LCS 长度都为 0。

4.2 按子问题规模填表

按照 $i=1,2,\ldots,m$ 和 $j=1,2,\ldots,n$ 的顺序计算每个状态：

1. 比较 $x_i$ 与 $y_j$；
2. 若相等，使用左上角状态；
3. 若不相等，比较上方状态和左方状态。

得到动态规划表：

右下角状态为：

$$c[7][6]=4$$

所以最长公共子序列的长度为：

$$\boxed{4}$$

5. 从动态规划表回溯

动态规划表给出了 LCS 的长度。要恢复一个具体的 LCS，需要从右下角状态 $(m,n)$ 逆向追踪状态转移。

5.1 回溯规则

当前位于状态 $(i,j)$。

规则一：当前元素相等

若 $x_i=y_j$：

1. 将该元素加入结果；
2. 向左上角移动到 $(i-1,j-1)$。

规则二：当前元素不相等

比较：

$$c[i-1][j] \qquad\text{与}\qquad c[i][j-1]$$

• 若上方较大，向上移动到 $(i-1,j)$，相当于舍弃 $x_i$；
• 若左方较大，向左移动到 $(i,j-1)$，相当于舍弃 $y_j$；
• 若两者相等，两个方向都可能通向某个 LCS。

平局与多解

只要求一个 LCS 时，可以规定固定的平局策略，例如优先向上。

若要求所有 LCS，则需要同时搜索两个方向，并对结果去重。

5.2 本例回溯

约定平局时优先向上。

回溯过程中依次记录：

A B C B

由于回溯方向是从序列末尾向前，因此需要反转：

B C B A

所以得到一个最长公共子序列：

$$\boxed{\text{BCBA}}$$

本例的 LCS 不唯一，BCAB 和 BDAB 也都是长度为 4 的最长公共子序列。

6. 伪代码

6.1 构造动态规划表

LCS-LENGTH(X, Y)
   m ← length(X)
   n ← length(Y)

   创建二维数组 c[0..m][0..n]

   for i ← 0 to m
      c[i][0] ← 0

   for j ← 0 to n
      c[0][j] ← 0

   for i ← 1 to m
      for j ← 1 to n
         if X[i] = Y[j]
            c[i][j] ← c[i-1][j-1] + 1
         else
            c[i][j] ← max(c[i-1][j], c[i][j-1])

   return c

6.2 回溯恢复一个 LCS

RECONSTRUCT-LCS(X, Y, c)
   i ← length(X)
   j ← length(Y)
   result ← empty list

   while i > 0 and j > 0
      if X[i] = Y[j]
         append X[i] to result
         i ← i - 1
         j ← j - 1

      else if c[i-1][j] ≥ c[i][j-1]
         i ← i - 1

      else
         j ← j - 1

   reverse(result)
   return result

6.3 完整算法

LCS(X, Y)
   c ← LCS-LENGTH(X, Y)
   sequence ← RECONSTRUCT-LCS(X, Y, c)

   return c[length(X)][length(Y)], sequence

7. 正确性要点

7.1 当前元素相等

若 $x_i=y_j$，则存在一个当前前缀的 LCS 以该相同元素结尾。

删除这个末尾元素后，剩余部分必须是两个更短前缀的 LCS，否则可以用更长的公共子序列替换它，从而与当前解的最优性矛盾。

因此：

$$c[i][j]=c[i-1][j-1]+1$$

7.2 当前元素不相等

若 $x_i\ne y_j$，则任意公共子序列不可能同时以这两个不同元素结尾。

因此，一个最优解至少满足以下情况之一：

• 不使用 $x_i$；
• 不使用 $y_j$。

于是：

$$c[i][j]=\max\{c[i-1][j],c[i][j-1]\}$$

这两个分支覆盖了所有可能的最优解。

8. 时间与空间复杂度

设两个序列的长度分别为 m 和 n。

8.1 时间复杂度

动态规划表共有 $(m+1)(n+1)$ 个状态，每个状态只进行常数次操作，因此填表时间为：

$$\Theta(mn)$$

回溯过程中，每一步至少使 i 或 j 减少 1，所以回溯时间为：

$$O(m+n)$$

总时间复杂度由填表阶段主导：

$$\boxed{\Theta(mn)}$$

8.2 空间复杂度

保存完整动态规划表需要：

$$\boxed{\Theta(mn)}$$

若只求 LCS 长度，可以使用滚动数组，将空间复杂度优化为：

$$\boxed{\Theta(\min(m,n))}$$

空间优化的限制

普通滚动数组不会保存完整的状态转移路径，因此不能直接用于回溯恢复具体 LCS。

若希望在线性空间内恢复 LCS，可以进一步学习 Hirschberg 算法。

9. 与最长公共子串的区别

详见 最长公共子串。

10. 易错点

• 混淆子序列与子串：子序列不要求连续，子串必须连续。
• 字符不等时向左上移动：字符不等时只能根据上方和左方状态决定方向。
• 将整张表最大值当作答案：LCS 的答案是右下角状态 $c[m][n]$。
• 回溯后忘记反转：回溯得到的字符顺序与最终 LCS 相反。
• 认为 LCS 必然唯一：平局状态可能对应多个不同的 LCS。
• 使用滚动数组后仍直接回溯：滚动数组没有保存完整路径。

一句话总结

当前元素相等时，选择该元素并向左上移动；当前元素不相等时，沿着较大的状态向上或向左移动。

11. 关联笔记

• 动态规划
• 最长公共子串
• Hirschberg 算法

12. 参考资料

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms, 3rd ed., Section 15.4, “Longest Common Subsequence”.
• Erik D. Demaine and Charles E. Leiserson. Introduction to Algorithms, Lecture 12: Dynamic Programming, 2005.
• 课程讲义：lec12.pdf