数据结构与算法 / 系统课时

求两个序列的最长公共子序列

求两个序列的最长公共子序列

给定两个序列,目标不是寻找连续片段,而是在保持相对顺序的前提下选出尽可能长的公共子序列。关键是把“大问题”拆成两个前缀之间的最优匹配长度,再根据末尾元素是否相等决定转移方向。

学习目标

  • 用 dp[i][j] 表示两个序列前缀的最长公共子序列长度
  • 推导末尾元素相等与不等时的两类状态转移
  • 用二维动态规划实现算法,并判断时间与空间复杂度

用两个前缀定义状态

设序列 a 长度为 m,序列 b 长度为 n。定义 dp[i][j] 为 a 的前 i 个元素与 b 的前 j 个元素的最长公共子序列长度。这样最终答案就是 dp[m][n]。

当任意一侧为空序列时,不可能形成非空公共子序列,因此 dp[0][j] = 0、dp[i][0] = 0。多出的第 0 行和第 0 列让后续转移无需额外判断越界。

从末尾元素推导转移

若 a[i - 1] == b[j - 1],这两个末尾元素可以一起加入某个最优公共子序列,因此 dp[i][j] = dp[i - 1][j - 1] + 1。

若末尾元素不同,它们不能在当前这一对位置上同时匹配。任意公共子序列至少会舍弃这两个末尾元素中的一个,所以只需比较“舍弃 a 的末尾”和“舍弃 b 的末尾”两个子问题:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

LCS 二维状态转移关系

这里没有遗漏“两个末尾都不选”的情况。因为 dp[i - 1][j - 1] 已包含在更大的两个前缀问题中,不会超过 dp[i - 1][j] 或 dp[i][j - 1],所以额外比较它不会改变结果。

用一张表观察状态增长

以 a = "abcde"、b = "ace" 为例,按行从上到下、按列从左到右填表:

dp 空 a c e
空 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

右下角 dp[5][3] = 3,对应公共子序列 "ace"。表格中的值只记录长度,不记录具体选择路径;如果题目还要求恢复子序列,需要从右下角按转移来源反向追踪。

实现并分析复杂度

下面的 Python 程序直接按定义填写二维状态表:

python
def lcs_length(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 每个状态只依赖左、上、左上三个已经计算过的位置。
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 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]


if __name__ == "__main__":
    print(lcs_length("abcde", "ace"))

预期输出

text
3

共有 (m + 1) × (n + 1) 个状态,每个状态只做常数次比较,因此时间复杂度为 O(mn),空间复杂度为 O(mn)。若只需要长度,可以只保留上一行与当前行,把空间降到 O(n);若还要恢复具体公共子序列,保留完整表通常更直观。

这类双序列题的关键不是背公式,而是先明确“两个前缀的答案”代表什么,再观察最后一对元素能否共同进入最优解。状态定义一旦稳定,边界和转移就会自然落到二维表上。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

求两个序列的最长公共子序列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通