数据结构与算法 / 系统课时
求两个序列的最长公共子序列
求两个序列的最长公共子序列
给定两个序列,目标不是寻找连续片段,而是在保持相对顺序的前提下选出尽可能长的公共子序列。关键是把“大问题”拆成两个前缀之间的最优匹配长度,再根据末尾元素是否相等决定转移方向。
学习目标
- 用
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])。

这里没有遗漏“两个末尾都不选”的情况。因为 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 程序直接按定义填写二维状态表:
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"))预期输出
3共有 (m + 1) × (n + 1) 个状态,每个状态只做常数次比较,因此时间复杂度为 O(mn),空间复杂度为 O(mn)。若只需要长度,可以只保留上一行与当前行,把空间降到 O(n);若还要恢复具体公共子序列,保留完整表通常更直观。
这类双序列题的关键不是背公式,而是先明确“两个前缀的答案”代表什么,再观察最后一对元素能否共同进入最优解。状态定义一旦稳定,边界和转移就会自然落到二维表上。