第53课 - 最长公共子序列 (LCS)

1. 学习目标

理解子序列与子串的区别，明确“最长公共子序列”（LCS）问题的定义。
掌握利用动态规划求解LCS问题的核心思想与状态转移方程。
能够使用二维数组实现计算LCS长度的算法。
理解并能够实现从DP表中回溯，找到具体的LCS序列。
能够分析LCS算法的时间与空间复杂度。

2. 核心概念

子序列 vs 子串： 这是一个关键区别。子串是字符串中连续的一段字符，如“ABCDE”的子串可以是“ABC”或“CDE”。而子序列是从原字符串中按顺序抽取的（不一定连续）字符序列，例如“ABCDE”的子序列可以是“ACE”（取第1、3、5个字符）或“AD”。

最长公共子序列（LCS）： 给定两个序列（通常为字符串），它们的“公共子序列”是指在两个序列中都出现，且顺序一致的子序列。其中长度最长的那个（或那些）就称为“最长公共子序列”。例如，对于序列 X = “ABCBDAB” 和 Y = “BDCAB”，它们的LCS是 “BCAB” 或 “BDAB”，长度为4。

为什么用动态规划？ 如果我们用暴力法，需要列举所有子序列并比较，时间复杂度是指数级的（O(2^n)），当序列较长时完全不可行。动态规划通过记录子问题的解，避免了重复计算，将时间复杂度降至多项式级别。

动态规划思路： 我们定义一个二维数组 dp，其中 dp[i][j] 表示序列 X 的前 i 个字符 (X[0..i-1]) 和序列 Y 的前 j 个字符 (Y[0..j-1]) 的LCS长度。状态转移依赖于 X 和 Y 的当前最后一个字符是否相等：

如果 X[i-1] == Y[j-1]（当前字符匹配），那么这个字符可以加入LCS。因此，dp[i][j] 就等于 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当前字符的LCS长度”和“忽略Y当前字符的LCS长度”中的较大值。即：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

边界条件： 当一个序列为空时（即 i=0 或 j=0），LCS长度为0。所以 dp 数组的第一行和第一列全部初始化为0。

3. 代码示例

下面是一个完整的Python实现，包括计算LCS长度和回溯找到具体序列。

def lcs(X, Y):
    """
    计算两个字符串X和Y的最长公共子序列。
    返回：(LCS长度, 具体的LCS字符串)
    """
    m, n = len(X), len(Y)
    
    # 创建 (m+1) x (n+1) 的DP表，初始化为0
    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的长度存储在 dp[m][n]
    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的一部分
            lcs_str.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            # 来自上方的解更大，向上移动
            i -= 1
        else:
            # 来自左方的解更大或相等，向左移动
            j -= 1
    
    # 因为是从后往前回溯，所以需要反转
    lcs_str = lcs_str[::-1]
    return lcs_length, ''.join(lcs_str)

# 测试代码
if __name__ == "__main__":
    X = "ABCBDAB"
    Y = "BDCAB"
    length, sequence = lcs(X, Y)
    print(f"字符串 X: {X}")
    print(f"字符串 Y: {Y}")
    print(f"最长公共子序列的长度: {length}")
    print(f"其中一组最长公共子序列: {sequence}")

输出示例：

字符串 X: ABCBDAB
字符串 Y: BDCAB
最长公共子序列的长度: 4
其中一组最长公共子序列: BCAB

代码解读：

dp 数组的维度为 (m+1) x (n+1)，用于存储所有子问题的解。
双重循环遍历两个字符串的所有字符组合，根据是否匹配应用状态转移方程。
回溯过程从右下角 (dp[m][n]) 开始，根据 dp 值的来源决定移动方向，并记录匹配的字符。

4. 实践练习

练习1（基础）： 给定字符串 X = “AGGTAB” 和 Y = “GXTXAYB”，请手动填充一个5x5的 dp 表（截取前5行5列），并计算完整的LCS长度。

预期输出： LCS长度应为4 (序列为 “GTAB”)。

练习2（进阶）： 修改上述代码，使其能够输出所有可能的LCS序列（提示：在回溯时，当 dp[i-1][j] == dp[i][j-1] 时，说明存在多个解，需要递归处理两个分支）。

输入： X = “ABC”, Y = “ACB”
预期输出： 所有LCS应为 ["AB", "AC"]。

练习3（应用）： LCS在生物信息学中用于DNA序列比对。假设有两个DNA片段： DNA1 = “ACCGGTCGAGTGCGCGGAAGCCGGCCGAA” DNA2 = “GTCGTTCGGAATGCCGTTGCTCTGTAAA” 编写程序计算它们的LCS长度。思考：这个结果说明了什么？

预期输出： 程序应输出一个整数（例如20）。

5. 常见错误

混淆子序列与子串： 错误地认为LCS必须在原字符串中连续。例如，认为 ABC 和 AC 的LCS是空，但实际上应该是 “AC”。
DP表索引错误： 容易将字符索引与DP表索引搞混。记住：X[i-1] 对应 dp 表的第 i 行。
忽略边界初始化： 忘记将 dp 数组的第一行和第一列初始化为0，这会导致状态转移方程在边界处出错。
回溯时只取一个方向： 在字符不匹配时，仅根据 dp[i-1][j] 和 dp[i][j-1] 的大小选择一个方向，这会导致找到一条LCS路径，但可能错过其他等长的LCS序列。如果题目要求所有序列，需要处理两者相等的情况。
只计算长度不输出序列： 很多初学者实现了 dp 表填充，但忽略了回溯步骤，无法输出具体的LCS字符串。

6. 小结

LCS问题：寻找两个序列共有的、保持原有顺序的最长子序列。
动态规划核心：使用二维数组 dp[i][j] 存储子问题解。
状态转移方程：
- 若 X[i-1] == Y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
时间复杂度：O(m * n)，其中m和n是两个序列的长度。
空间复杂度：O(m * n)。可通过滚动数组优化至 O(min(m, n))。
回溯：通过从 dp[m][n] 出发，根据 dp 值的来源反向遍历，即可构造出具体的LCS序列。
应用：LCS是许多文本差异比较、版本控制、生物序列比对算法的基础。

练习编辑器

rust