最长公共子序列

1. 核心概念定义

什么是子序列 (Subsequence)？

一个序列 S 的子序列，是从 S 中删除零个或多个元素后，保持剩余元素相对顺序不变所得到的新序列。

例子：对于序列 S = "ABCBDAB"
- "ACB" 是一个子序列 (删除了 ‘B’, ‘D’, ‘A’, ‘B’)
- "BDAB" 是一个子序列 (删除了 ‘A’, ‘C’, ‘B’)
- "ACD" 不是一个子序列，因为 ‘D’ 出现在 ‘C’ 之前，改变了相对顺序。
- "ACE" 不是一个子序列，因为原序列中没有 ‘E’。

关键点：不要求连续，但要求顺序。

什么是公共子序列 (Common Subsequence)？

如果一个序列 Z 同时是序列 X 和序列 Y 的子序列，那么 Z 就是 X 和 Y 的一个公共子序列。

例子：
- X = "ABCBDAB"
- Y = "BDCABA"
- "BA" 是一个公共子序列 (在 X 中是 ABCAB，在 Y 中是 BDCABA)
- "BCA" 是一个公共子序列
- "BCBA" 也是一个公共子序列

什么是LCS (Longest Common Subsequence)？

在所有公共子序列中，长度最长的那个（或那些）序列，就是最长公共子序列。

例子：对于上面的 X 和 Y，"BCBA" 和 "BDAB" 都是长度为 4 的公共子序列。它们就是 LCS。
注意：LCS 可能不唯一，但其长度是唯一的。我们通常首先关心的是这个唯一的长度。

2. 与“最长公共子串”的区别

这是一个非常常见的混淆点，必须厘清。

子序列 (Subsequence)：元素不要求连续。
子串 (Substring)：元素必须连续。
例子：X = "ABCBDAB", Y = "BDCABA"
- 最长公共子序列 (LCS) 是 "BCBA" 或 "BDAB"，长度为 4。
- 最长公共子串 (Longest Common Substring) 是 "AB"，长度为 2。

LCS 问题通常比最长公共子串问题更复杂一些。

3. 问题求解：动态规划 (DP)

暴力法（枚举 X 的所有子序列，然后检查它们是否也是 Y 的子序列）的复杂度是指数级的 ( $O(2^m \cdot n)$ )，完全不可行。动态规划是解决此问题的标准方法。

为什么使用动态规划？

LCS 问题符合动态规划的两个核心特征：

最优子结构 (Optimal Substructure)：一个问题的最优解包含其子问题的最优解。LCS(X, Y) 的解依赖于 LCS(X的前缀, Y的前缀) 的解。
重叠子问题 (Overlapping Subproblems)：在递归求解过程中，许多相同的子问题会被反复计算。DP 通过存储子问题的解来避免重复计算。

DP 解法核心思想

我们通过构建一个二维表格（DP Table）来记录子问题的解。

第一步：定义 DP 数组（状态定义）

我们创建一个二维数组 dp[i][j]，它表示： dp[i][j] = 序列 X 的前 i 个字符 (X[0...i-1]) 与序列 Y 的前 j 个字符 (Y[0...j-1]) 的最长公共子序列的长度。

我们的最终目标是求 dp[m][n]，其中 m 是 X 的长度，n 是 Y 的长度。

第二步：找出状态转移方程（递推关系）

这是动态规划的核心。对于 dp[i][j]，我们需要考虑 X 的第 i 个字符 (X[i-1]) 和 Y 的第 j 个字符 (Y[j-1])。

有两种情况：

如果 X[i-1] == Y[j-1]：这两个字符相同，那么它们一定可以作为公共子序列的一部分。所以，LCS 的长度就是 X 的前 i-1 个字符和 Y 的前 j-1 个字符的 LCS 长度再加 1。 dp[i][j] = dp[i-1][j-1] + 1
如果 X[i-1] != Y[j-1]：这两个字符不相同，它们不能同时作为LCS的末尾。所以我们必须“丢弃”一个：
- 要么丢弃 X[i-1]，在 X 的前 i-1 个字符和 Y 的前 j 个字符中找 LCS。其长度为 dp[i-1][j]。
- 要么丢弃 Y[j-1]，在 X 的前 i 个字符和 Y 的前 j-1 个字符中找 LCS。其长度为 dp[i][j-1]。我们选择两者中较大的那个。 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

第三步：初始化

为了方便计算 dp[i-1] 或 dp[j-1]，我们通常将 DP 表的大小设为 (m+1) x (n+1)。 dp[0][j] 表示 X 为空串时与 Y 的任意前缀的LCS，长度显然为 0。 dp[i][0] 表示 Y 为空串时与 X 的任意前缀的LCS，长度也显然为 0。所以，DP 表的第一行和第一列都初始化为 0。

4. 实例详解：一步步构建 DP 表

我们用 X = "ABCBDAB" (m=7) 和 Y = "BDCABA" (n=6) 来走一遍流程。

DP 表大小为 (7+1) x (6+1) 即 8x7。

初始化：


“”“”“”B   D   C   A   B   A
""""0   0   0   0   0   0   0
A     0
B     0
C     0
B     0
D     0
A     0
B     0

开始填充 (只展示几个关键步骤):

dp[1][1] (A vs B): X[0] != Y[0], dp[1][1] = max(dp[0][1], dp[1][0]) = max(0, 0) = 0
dp[1][4] (A vs BDCA): X[0] == Y[3] (A == A), dp[1][4] = dp[0][3] + 1 = 0 + 1 = 1
dp[2][1] (AB vs B): X[1] == Y[0] (B == B), dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1
dp[2][2] (AB vs BD): X[1] != Y[1] (B != D), dp[2][2] = max(dp[1][2], dp[2][1]) = max(0, 1) = 1
… …

最终完整的 DP 表：


"" B(0) D(1) C(2) A(3) B(4) A(5)
""(0)  0   0    0    0    0    0    0
A(0)   0   0    0    0    1    1    1
B(1)   0   1    1    1    1    2    2
C(2)   0   1    1    2    2    2    2
B(3)   0   1    1    2    2    3    3
D(4)   0   1    2    2    2    3    3
A(5)   0   1    2    2    3    3    4
B(6)   0   1    2    2    3    4    4

右下角的值 dp[7][6] = 4。所以，LCS 的长度为 4。

5. 回溯：如何找出LCS本身

DP 表只给了我们长度，要找到具体的序列，需要从 dp[m][n] 开始回溯。

从 (i, j) = (m, n) 开始。
如果 X[i-1] == Y[j-1]：说明这个字符是 LCS 的一部分。将此字符加入结果中，然后移动到 (i-1, j-1)。
如果 X[i-1] != Y[j-1]：
- 比较 dp[i-1][j] 和 dp[i][j-1]。
- 如果 dp[i-1][j] > dp[i][j-1]，说明LCS来自于上方，移动到 (i-1, j)。
- 如果 dp[i-1][j] < dp[i][j-1]，说明LCS来自于左方，移动到 (i, j-1)。
- 如果 dp[i-1][j] == dp[i][j-1]，可以任选一个方向移动（向上或向左）。选择不同方向可能导致找到不同的LCS（如果存在多个）。
重复此过程，直到 i 或 j 为 0。
因为是反向构建的，最后需要将结果字符串反转。

回溯示例 (从 dp[7][6]=4 开始):

(7, 6): X[6](‘B’) != Y[5](‘A’). dp[6][6](4) > dp[7][5](4) 不成立，dp[6][6](4) == dp[7][5](4)。我们向左移动到 (7, 5)。
(7, 5): X[6](‘B’) == Y[4](‘B’). 这是LCS的一部分。记录 ‘B’，移动到 (6, 4)。LCS: B
(6, 4): X[5](‘A’) == Y[3](‘A’). 这是LCS的一部分。记录 ‘A’，移动到 (5, 3)。LCS: AB
(5, 3): X[4](‘D’) != Y[2](‘C’). dp[4][3](2) == dp[5][2](2)。向上移动到 (4, 3)。
(4, 3): X[3](‘B’) != Y[2](‘C’). dp[3][3](2) == dp[4][2](2)。向上移动到 (3, 3)。
(3, 3): X[2](‘C’) == Y[2](‘C’). 这是LCS的一部分。记录 ‘C’，移动到 (2, 2)。LCS: CAB
(2, 2): X[1](‘B’) != Y[1](‘D’). dp[1][2](1) < dp[2][1](1) 不成立，相等。向上移动到 (1, 2)。
(1, 2): X[0](‘A’) != Y[1](‘D’). dp[0][2](0) < dp[1][1](0) 不成立，相等。向上移动到 (0,2)。
i=0, 停止。

反转后得到 BCAB？等一下，我在回溯第1步和第6/7/8步做了任意选择，如果选择不同，结果也会不同。让我们试试另一条路径。

另一条回溯路径 (从 dp[7][6]=4 开始):

(7, 6): X[6](‘B’) != Y[5](‘A’). dp[6][6](4) == dp[7][5](4)。这次我们向上移动到 (6, 6)。
(6, 6): X[5](‘A’) == Y[5](‘A’). 记录 ‘A’, 移到 (5, 5). LCS: A
(5, 5): X[4](‘D’) != Y[4](‘B’). dp[4][5](3) == dp[5][4](3). 向上移到 (4, 5).
(4, 5): X[3](‘B’) == Y[4](‘B’). 记录 ‘B’, 移到 (3, 4). LCS: BA
(3, 4): X[2](‘C’) != Y[3](‘A’). dp[2][4](2) == dp[3][3](2). 向左移到 (3, 3).
(3, 3): X[2](‘C’) == Y[2](‘C’). 记录 ‘C’, 移到 (2, 2). LCS: CBA
(2, 2): X[1](‘B’) != Y[1](‘D’). dp[1][2](1) < dp[2][1](1) 不成立，相等。向左移到 (2, 1).
(2, 1): X[1](‘B’) == Y[0](‘B’). 记录 ‘B’, 移到 (1, 0). LCS: BCBA
j=0, 停止。

反转后得到 BCBA。这就是我们前面提到的一个LCS。

6. 代码实现 (Python)


def lcs(X, Y):
    m = len(X)
    n = len(Y)
 
    # 创建 DP 表，大小为 (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    # 填充 DP 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
    # LCS 的长度在右下角
    lcs_length = dp[m][n]
 
    # 回溯以找到 LCS 字符串
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_str.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    # 因为是反向添加的，所以需要反转
    return lcs_length, "".join(reversed(lcs_str))
 
# --- 测试 ---
X = "ABCBDAB"
Y = "BDCABA"
length, sequence = lcs(X, Y)
print(f"字符串1: {X}")
print(f"字符串2: {Y}")
print(f"最长公共子序列的长度: {length}") # 输出: 4
print(f"一个最长公共子序列是: {sequence}") # 输出: BCBA (或 BDAB，取决于回溯时的选择)

7. 复杂度分析

时间复杂度: O(m * n)。我们需要填充一个 m x n 的表格，每个单元格的计算是常数时间。
空间复杂度: O(m * n)。我们需要一个 m x n 的表格来存储所有子问题的解。

8. 空间优化

如果我们只关心LCS的长度，而不关心LCS本身，可以进行空间优化。

观察状态转移方程 dp[i][j] 的计算只依赖于 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]。这意味着，计算第 i 行时，我们只需要第 i-1 行的信息。

因此，我们不需要存储整个 m x n 的表格，只需要存储两行（当前行和上一行）就足够了。这样空间复杂度可以降到 O(min(m, n))。

更进一步，我们甚至可以只用一个一维数组来完成。在计算第 i 行时，一维数组 dp[j] 存储的是上一行（i-1行）的值，然后我们用它来更新当前行（i行）的值。

注意：这种空间优化方法，会丢失构建完整DP表的信息，导致无法通过回溯找到LCS序列本身。若要同时实现空间优化和找到LCS序列，需要使用更复杂的算法（如 Hirschberg’s algorithm）。

9. 实际应用

LCS 是一个基础且强大的算法，应用广泛：

版本控制系统 (Git/SVN)：diff 命令用来比较文件差异，其核心原理就类似于LCS，找出两个文件版本之间的共同部分，从而只显示、存储变化的部分。
生物信息学：比较DNA、RNA或蛋白质序列。序列的相似度可以揭示物种的进化关系或基因的功能。LCS是衡量序列相似度的重要指标之一。
数据比较与合并：在各种文本编辑器、IDE中，比较两个文档的异同。
抄袭检测：通过计算两篇文档的LCS长度，可以初步判断它们的相似程度。