数据结构与算法 / 系统课时
用二维状态处理字符串匹配
用二维状态处理字符串匹配
两个字符串一起变化时,只用一个下标往往无法描述“各自处理到哪里”。二维动态规划把两个前缀位置同时放进状态,让匹配、跳过、替换等操作都有明确来源。本篇以最长公共子序列为主例,并把同一建模方式迁移到编辑距离和其他前缀匹配问题。
学习目标
- 用两个位置维度定义字符串前缀状态
- 从字符是否相等推导二维状态的转移来源
- 根据依赖方向确定初始化与遍历顺序
二维状态为什么适合字符串匹配
给定字符串 s 和 t,常见问题都会同时问“s 处理到第几个字符”和“t 处理到第几个字符”。因此可以定义:
dp[i][j] 表示只考虑 s 的前 i 个字符和 t 的前 j 个字符时的答案。
这个定义把两个字符串都截成前缀,状态 (i, j) 就是网格中的一个格子。转移通常来自左侧 (i, j-1)、上侧 (i-1, j) 或左上角 (i-1, j-1),具体选择取决于当前两个字符是否匹配以及题目允许什么操作。

二维表的第 0 行和第 0 列代表其中一个字符串为空。它们不是额外技巧,而是把边界情况纳入统一状态定义:只要初始化正确,后面的转移就不需要不断判断是否越界。
最长公共子序列的转移
最长公共子序列要求字符相对顺序不变,但不要求连续。定义 dp[i][j] 为 s[:i] 与 t[:j] 的最长公共子序列长度。
若 s[i-1] == t[j-1],这两个字符可以共同接在更短前缀的答案后面:
若二者不同,当前字符至少有一个不能出现在同一个最优公共子序列中,因此比较“丢掉 s 当前字符”和“丢掉 t 当前字符”:
因为当前格只依赖左、上、左上三个已经计算过的状态,所以按行从左到右填表即可。
写出完整实现并验证
下面的程序计算两个字符串的最长公共子序列长度,并打印最终二维表,便于检查边界与转移是否符合定义。
def lcs_length(s, t):
rows, cols = len(s) + 1, len(t) + 1
dp = [[0] * cols for _ in range(rows)]
for i in range(1, rows):
for j in range(1, cols):
if s[i - 1] == t[j - 1]:
# 两个当前字符匹配,答案来自左上角再加 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[-1][-1], dp
if __name__ == "__main__":
length, table = lcs_length("abcde", "ace")
print("length:", length)
for row in table:
print(row)预期输出
length: 3
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]最后一个格子是 3,对应公共子序列 ace。如果某一行或某一列突然出现不符合单调性的值,通常说明字符下标 i-1、j-1 与状态下标 i、j 混用了。
同一张二维表如何迁移到其他题
二维字符串 DP 的关键不是记住某个公式,而是先回答“状态代表哪两个前缀”,再根据允许操作选择来源。
| 问题 | dp[i][j] 常见含义 |
主要来源 |
|---|---|---|
| 最长公共子序列 | 两个前缀的 LCS 长度 | 左、上、左上 |
| 编辑距离 | 把 s[:i] 变成 t[:j] 的最少操作数 |
删除、插入、替换对应的三个邻格 |
| 通配或正则式匹配 | 两个前缀是否能够匹配 | 由当前模式字符决定左、上或左上依赖 |
| 区间或分段匹配 | 两个边界或前缀组合下的最优值 | 依题意增加区间长度或分割点维度 |
例如编辑距离中,若当前字符相等,通常直接继承左上角;若不同,则从删除、插入、替换三个操作中取最小值再加 1。它与 LCS 使用的是同一个二维前缀坐标系,只是状态值和转移规则不同。
检查二维字符串 DP 的三个边界
最常见的错误集中在状态定义与下标错一位:
- 第 0 行和第 0 列代表什么。 LCS 中它们全是 0;编辑距离中通常需要初始化为
0,1,2,...,因为空串转换到长度为j的前缀需要j次插入。 - 字符下标与状态下标要错开一位。 状态
i表示前i个字符,因此当前字符是s[i-1],不是s[i]。 - 遍历方向必须覆盖依赖。 如果当前格依赖左、上和左上,就必须保证这些格子已经计算完成;标准二维表按行从左到右即可。
掌握二维字符串 DP 后,真正可复用的是“两个前缀位置组成坐标”的建模方式。只要先写清 dp[i][j] 的含义,再标出当前格能从哪些已知状态转移,初始化、遍历顺序和边界通常都会自然确定。