Part 5.3：最长公共子序列 (LCS)

引言：寻找代码的“相似基因”

想象一下，你正在使用 Git 进行代码版本控制。当你执行 git diff 命令时，系统是如何清晰地标出两段代码之间的差异与相同之处的？或者，在生物信息学中，科学家是如何比较两条 DNA 序列，找出它们之间最长的共同“基因片段”，以判断物种的亲缘关系的？

这些问题的核心，都指向了一个经典的算法问题——**最长公共子序列 (Longest Common Subsequence, LCS)**。

给定两个序列（通常是字符串），LCS 问题旨在找到它们共有的、最长的子序列。回顾一下，子序列可以不连续，但必须保持原有的相对顺序。

例如，对于两个字符串：

S1 = "ABCBDAB"
S2 = "BDCAB"

它们的一个公共子序列是 "BCAB"，另一个是 "BDAB"。这两个子序列的长度都是 4，它们就是最长公共子序列。

为什么 LCS 如此重要？

面试价值：LCS 是二维动态规划的入门典范，几乎是所有字符串 DP 问题的基础。在面试中，能流畅地写出 LCS 的代码并解释其原理，是展现你 DP 思维和问题分解能力的重要标志。
工程价值：LCS 及其变种在各种“比对”场景中无处不在。除了 diff 工具和基因序列比对，它还应用于文本相似度计算、抄袭检测、数据压缩等领域。

本文将带你从零开始，构建 LCS 问题的动态规划解法，不仅求出最长长度，还要学会如何回溯路径，找到那个具体的子序列。

背景知识：二维动态规划

LCS 是一个典型的二维动态规划问题。与之前我们接触的一维 DP (如 LIS) 不同，LCS 的状态依赖于两个变化的维度——即两个字符串的当前位置。

因此，我们需要一个二维的 dp 表来存储子问题的解。dp[i][j] 通常表示与第一个字符串的前 i 个字符和第二个字符串的前 j 个字符相关的某种最优解。

理解二维 DP 的关键在于：

清晰地定义 dp[i][j] 的含义。
找到 dp[i][j] 与其相邻状态（如 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]）之间的递推关系。

详细算法原理

1. 算法的“直觉”：逐步对齐，寻找匹配

假设我们有两个字符串 s1 和 s2，我们想要求解 lcs(s1, s2)。动态规划的思想是把大问题分解为小问题。我们从两个字符串的末尾开始看，即 s1 的最后一个字符 s1[i-1] 和 s2 的最后一个字符 s2[j-1]。

此时，只有两种情况：

末尾字符相同：s1[i-1] == s2[j-1]。
太棒了！我们找到了一个公共字符。这个字符必然可以作为 LCS 的一部分（而且是最后一部分）。为什么？如果它不是 LCS 的一部分，那么我们可以把它添加到 LCS 的末尾，得到一个更长的 LCS，这与“最长”的定义矛盾。
所以，在这种情况下，lcs(s1[0..i-1], s2[0..j-1]) 的长度就等于 1 + lcs(s1[0..i-2], s2[0..j-2])。
末尾字符不同：s1[i-1] != s2[j-1]。
这意味着这两个字符不可能同时出现在 LCS 的末尾。LCS 要么存在于 s1 的前 i-1 个字符与 s2 的全部字符中，要么存在于 s1 的全部字符与 s2 的前 j-1 个字符中。我们不知道哪个更长，所以我们都算一下，取其中较大的那个。
所以，lcs(s1[0..i-1], s2[0..j-1]) 的长度等于 max( lcs(s1[0..i-2], s2[0..j-1]), lcs(s1[0..i-1], s2[0..j-2]) )。

通过这种方式，我们不断地将问题规模缩小，直到遇到空字符串（LCS 长度为 0），这就是递归的出口。

2. 严谨原理：状态定义与状态转移方程

状态定义：dp[i][j] 表示字符串 s1 的前 i 个字符（s1[0...i-1]）与字符串 s2 的前 j 个字符（s2[0...j-1]）的最长公共子序列的长度。
状态转移方程：
- 如果 s1[i-1] == s2[j-1]：
  dp[i][j] = dp[i-1][j-1] + 1
- 如果 s1[i-1] != s2[j-1]：
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])
**初始化 (Base Case)**：
创建一个 (m+1) x (n+1) 的 dp 表，其中 m 和 n 分别是 s1 和 s2 的长度。第 0 行和第 0 列都初始化为 0，因为任何字符串与空字符串的 LCS 长度都是 0。

步骤分解 (Step-by-step)

创建 DP 表：创建一个 (m+1) x (n+1) 的二维数组 dp，并全部初始化为 0。
外层循环：遍历 s1 的每个字符 i，从 1 到 m。
内层循环：遍历 s2 的每个字符 j，从 1 到 n。
状态转移：在循环体内，根据 s1[i-1] 和 s2[j-1] 是否相等，应用相应的状态转移方程来填写 dp[i][j]。
返回结果：循环结束后，dp[m][n] 就是 LCS 的最大长度。

动画式案例

s1 = "ace", s2 = "abcde"

1. 初始化 dp 表 (4x6)

      ""  a  b  c  d  e
""   [ 0, 0, 0, 0, 0, 0 ]
a    [ 0, 0, 0, 0, 0, 0 ]
c    [ 0, 0, 0, 0, 0, 0 ]
e    [ 0, 0, 0, 0, 0, 0 ]

2. 填表过程 (i=1, s1[0]=’a’)

dp[1][1]: s1[0]=='a', s2[0]=='a'. dp[1][1] = dp[0][0] + 1 = 1
dp[1][2]: s1[0]!='b'. dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1
… (第一行都会是 1)

3. 填表过程 (i=2, s1[1]=’c’)

dp[2][1]: s1[1]!='a'. dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1
dp[2][2]: s1[1]!='b'. dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1
dp[2][3]: s1[1]=='c'. dp[2][3] = dp[1][2] + 1 = 1 + 1 = 2
…

最终 DP 表

      ""  a  b  c  d  e
""   [ 0, 0, 0, 0, 0, 0 ]
a    [ 0, 1, 1, 1, 1, 1 ]
c    [ 0, 1, 1, 2, 2, 2 ]
e    [ 0, 1, 1, 2, 2, 3 ]

最终答案是 dp[3][5] = 3。

Python 实现

def longest_common_subsequence(s1: str, s2: str) -> int:
    """
    计算两个字符串的最长公共子序列的长度。
    """
    m, n = len(s1), len(s2)
    # dp[i][j]: s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                # 末尾字符相同，LCS 长度加 1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 末尾字符不同，取两种情况的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# --- 案例测试 ---
s1 = "ABCBDAB"
s2 = "BDCAB"
print(f"LCS 的长度是: {longest_common_subsequence(s1, s2)}") # 输出: 4

复杂度推导过程

时间复杂度: O(m * n)。我们需要填充一个 m x n 的二维 dp 表，每个单元格的计算是 O(1) 的。
空间复杂度: O(m * n)。我们需要一个 (m+1) x (n+1) 的二维 dp 表。

与 0-1 背包问题类似，LCS 也可以进行空间优化，将空间复杂度降低到 O(min(m, n))，但这里我们暂时不展开，因为二维 dp 表对于后续的回溯路径至关重要。

扩展：如何找到 LCS 本身？

dp 表不仅告诉我们 LCS 的长度，还隐藏了 LCS 的具体内容。我们可以通过从 dp[m][n] 开始回溯来找到它。

回溯策略：

从 (i, j) = (m, n) 开始。
如果 s1[i-1] == s2[j-1]，说明这个字符是 LCS 的一部分。我们将它加入结果，然后移动到 (i-1, j-1)。
如果 s1[i-1] != s2[j-1]，我们比较 dp[i-1][j] 和 dp[i][j-1]。
- 如果 dp[i-1][j] > dp[i][j-1]，说明 LCS 来自于 s1 的前 i-1 个字符，我们移动到 (i-1, j)。
- 否则，移动到 (i, j-1)。
重复此过程，直到 i 或 j 为 0。

Python 实现 (回溯)

def get_lcs_sequence(s1: str, s2: str) -> str:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 从 dp 表的右下角开始回溯
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs_str.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    # 因为是倒序添加的，所以需要反转
    return "".join(reversed(lcs_str))

# --- 案例测试 ---
s1 = "ABCBDAB"
s2 = "BDCAB"
print(f"LCS 序列是: {get_lcs_sequence(s1, s2)}") # 输出: BCAB 或 BDAB (取决于 max 的选择)

总结

最长公共子序列 (LCS) 是二维动态规划的一个完美范例。它教会我们如何处理涉及两个序列的匹配问题，其思想是许多更复杂字符串 DP 问题的基础。

本文核心要点

✅ 核心思想：通过比较两个序列的末尾字符，将问题分解为更小的子问题。
✅ 状态定义：dp[i][j] 是 s1 前 i 个字符和 s2 前 j 个字符的 LCS 长度。
✅ 状态转移方程：

s1[i-1] == s2[j-1] => dp[i][j] = dp[i-1][j-1] + 1
s1[i-1] != s2[j-1] => dp[i][j] = max(dp[i-1][j], dp[i][j-1])
✅ 复杂度：时间 O(m*n)，空间 O(m*n)。
✅ 回溯路径：可以通过从 dp 表的右下角回溯，找到具体的 LCS 序列。

掌握了 LCS，你就掌握了二维 DP 的基本套路。在下一篇文章中，我们将探讨另一个有趣的 DP 问题——区间 DP，学习如何解决在一个区间上进行最优决策的问题。

大学算法全体系 > Part 5：动态规划

#动态规划 #DP #最长公共子序列 #LCS #字符串算法

Part 5.3：最长公共子序列 (LCS)

https://hjjjkh.github.io/posts/935c7c18

作者

李国强

发布于

2025年11月15日

许可协议

Part 2.7：并查集：高效处理“朋友圈”问题上一篇

Part 5.2：最长上升子序列 (LIS) 下一篇