动态规划详解：字符串最短编辑距离原理、实现与优化

字符串最短编辑距离说实话是个既简单又唬人的经典动态规划问题。说它简单因为实现了的核心代码往往连二十行都不到说它唬人因为几乎每次面试或期末复习都会有人被三个操作的状态转移绕晕。dp[i][j]到底什么意思为什么插入对应dp[i][j-1] 1删除偏偏对应dp[i-1][j] 1这些问题不把状态定义和推导过程彻底吃透背了模板也白搭。这篇文章就围绕“动态规划之字符串最短编辑距离”这一个点把问题背景、手工推演、代码实现、空间优化和工程上的坑全部摊开讲。先给还没接触过的朋友补个基础。编辑距离也叫 Levenshtein 距离衡量的是把一个字符串 A 变成另一个字符串 B 所需的最少编辑次数。这里说的编辑操作被严格限定为三种插入一个字符、删除一个字符、替换一个字符每操作一次计一步。比如“cat”变成“dog”三个字母都不一样最直接的方案就是三次替换距离为 3。而“abc”变成“abcde”只需要在尾部插入 d 和 e距离为 2。看起来简单的规则背后却能撑起搜索纠错、代码查重、DNA 序列比对、数据清洗里的一大批真实需求。这篇内容适合三类人。一是刚开始练动态规划、被各种背包模板搞得晕头转向的初学者二是要在项目里实现文本相似度或模糊匹配需要自己评估和写一个距离算法的开发者三是正在复习应对考试的学生。不管你属于哪一类跟着我走一遍完整的推导过程后面遇到任何字符串 DP 题思路都会清晰很多。1. 项目概述与核心需求1.1 编辑距离的操作定义与最小化目标先把三个操作彻底说清楚。假设手里有字符串 a目标是把 a 变成字符串 b。第一条规则是插入可以在 a 的任意位置插入一个新字符比如把“ab”变成“acb”在中间插入 c 就算一次操作。第二条规则是删除删掉 a 里任意一个字符比如“abc”删掉 b 得到“ac”也是一次操作。第三条规则是替换把某个位置的字符直接换成另一个字符比如“abc”中的 b 换成 x得到“axc”同样算一次操作。三种操作可以混合使用顺序也不限。最短编辑距离的定义就是存在一系列操作能让 a 恰好变成 b且总操作次数最小这个最小次数就是距离。有两个容易想偏的细节。第一操作看似发生在任意位置但后面我们会发现任何“在中间插入或删除”的行为都可以等价地归约到对字符串某个末端的处理上这才使得动态规划有机会落地。第二如果 a 和 b 有一部分字符本来就完全相同那这部分绝不应该被删除再重新插入最优解里不会出现这种自残式操作。这两个直觉会在状态转移时被自然体现。1.2 为什么这道题处处可见很多同学以为编辑距离只是算法题实际工程里它的出场频率相当高。搜索引擎里输错关键词系统给出的“你是不是想找”提示候选排序时常常就要计算用户输入与候选词之间的编辑距离论文查重、代码查重系统里把文章切分成句子或 token 后再与目标库比对用的也是这个框架生物信息学中比较两条 DNA 序列或蛋白质序列的相似度同样依赖这一类 DP 距离模型。能成为面试题常客是因为它考察的东西足够综合能不能从问题中抽象出状态和决策能不能处理好空串这种边界情况能不能进一步考虑时间空间优化。这些能力不是靠背模板能获得的编辑距离恰好能把它们全部串起来。从这个角度看花一个晚上把这个问题的原理彻底推一遍一点都不亏。2. 从暴力思路到动态规划关键窗口在哪里2.1 直接穷举为什么不可行一个很自然的第一反应是我直接递归枚举所有操作组合再挑步数最少的路径不就行了代码逻辑也没毛病比如下面这样的写法def edit_distance_brute(a, b): if not a: return len(b) if not b: return len(a) if a[-1] b[-1]: return edit_distance_brute(a[:-1], b[:-1]) return 1 min( edit_distance_brute(a[:-1], b), edit_distance_brute(a, b[:-1]), edit_distance_brute(a[:-1], b[:-1]) )逻辑正确性能没法看。每一步最多产生 3 个递归分支字符串长度为 n 时粗略上界是 3^n 级别的调用次数。n10 时已经接近六万次n20 时直接奔着几十亿去了根本没法在实际场景里运行。哪怕真实分支因为字符相等会被截断最坏情况下依旧是指数爆炸。更麻烦的是这些分支里有海量重复计算。举个例子算“abc”和“xyz”的距离时不同的递归路径可能都会走到edit_distance(ab, xy)这个子状态但每一轮都在重新算。如果能把这些中间结果记下来复杂度就能从指数级降到多项式级这是动态规划第一个核心思路。2.2 抓住“最后一次操作”的思考角度暴力递归容易乱是因为把所有操作都想象成了可以发生在任意位置的序列。换一个角度只看最后一次操作发生在哪里。假设现在要把 a 的前 i 个字符变成 b 的前 j 个字符观察 a[i-1] 和 b[j-1] 这两个末尾字符。如果两者相等那这一步根本不需要编辑只需要把 a 的前 i-1 个字符变成 b 的前 j-1 个字符就行。如果两者不相等那么最后一步只有三种可能删除 a[i-1]代价加一然后继续解决“a 前 i-1 个字符变成 b 前 j 个字符”的子问题。在 a 末尾插入 b[j-1]代价加一然后继续解决“a 前 i 个字符变成 b 前 j-1 个字符”的子问题。用 b[j-1] 替换掉 a[i-1]代价加一然后继续解决“a 前 i-1 个字符变成 b 前 j-1 个字符”的子问题。把“最后一个字符怎么处理”当成决策点大问题就顺理成章被拆成三个规模更小的子问题。这个观察是整个推导的灵魂比死记公式有用得多。以后再遇到字符串编辑类问题都可以先想“最后一个字符是相等还是不相等”。2.3 为什么可以大胆复用子问题的解用动态规划前得先确认两个性质成立最优子结构和重叠子问题。最优子结构指的是大问题的最优解里包含子问题的最优解。编辑距离满足这一点。可以用反证想如果某个子问题还能用更少的操作数完成那把这个更优的子方案替换回原方案总操作数只会更少这跟“原方案已经是最优”矛盾。所以每个dp[i][j]都必须是建立在子问题最优解之上的。重叠子问题更直观。从“kitten”变成“sitting”的过程中像“ki”变“sit”、“kit”变“si”这类前缀组合会被多条递归路径反复遇到。子问题总量其实就是 (n1) × (m1) 个并不随操作顺序爆炸。动态规划的做法就是把每个子问题的结果存进表里同一个状态只算一次后面直接查表。两个性质都成立DP 才既合法又高效。3. 状态定义与转移方程推导3.1 dp[i][j] 到底代表什么状态定义是整道题的基础也是最容易绕晕的地方。我们把dp[i][j]定义为把字符串 a 的前 i 个字符变成字符串 b 的前 j 个字符所需的最少编辑次数。注意这里 i 和 j 表示的是长度不是下标。比如dp[2][3]表示 a 的前两个字符与 b 的前三个字符之间的距离。为什么要用长度而不是下标因为要为空串预留位置。当 i0 时a 的前 0 个字符就是空串把空串变成 b 的前 j 个字符只能不断插入所以dp[0][j] j。同理dp[i][0] i表示把 a 的前 i 个字符全部删掉。边界条件汇总dp[0][0] 0空串变空串零操作。dp[0][j] j对所有 0 ≤ j ≤ m。dp[i][0] i对所有 0 ≤ i ≤ n。很多新手代码跑出离谱结果八成就是边界没设对或者把dp[0][0]想当然写成了 1。空串这个特殊情况是后续一切推导的起点。3.2 转移方程的三条来源推导假设 a 长度为 nb 长度为 m。当a[i-1] b[j-1]时末尾字符不需要任何编辑直接沿用dp[i-1][j-1]。当两者不相等时从三个方向转移dp[i-1][j] 1对应删除操作。含义是a 的前 i-1 个字符已经成功变成 b 的前 j 个字符但 a[i-1] 还多出来必须删掉。dp[i][j-1] 1对应插入操作。含义是a 的前 i 个字符已经成功变成 b 的前 j-1 个字符但 b[j-1] 还没补上所以要插入它。dp[i-1][j-1] 1对应替换操作。含义是a 的前 i-1 个字符已经变成 b 的前 j-1 个字符但最后一个字符对不上直接替换。三者取最小就是dp[i][j]的最优值。公式长这样dp[i][j] dp[i-1][j-1] 若 a[i-1] b[j-1] dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 否则这里有个值得说透的细节不要试图在字符相等时也去做删除、插入、替换。理论上当然能做但操作数只会更大因为末尾字符本来就能直接用何必先破坏再修复所以标准实现里匹配分支直接赋值不参与 min 比较。3.3 填表顺序为什么可以无脑两层循环dp[i][j]依赖左上角dp[i-1][j-1]、上方dp[i-1][j]和左边dp[i][j-1]。只要外层循环按 i 从小到大、内层按 j 从小到大填每一步需要用到的三个格子都已经有值了。这个特性让编辑距离的实现变得非常简单不需要处理复杂的依赖顺序也不用递归后序遍历两个 for 循环从头写到尾就够了。可以把整张表想象成一个棋盘从左往右、从上往下扫描永远不需要回头补填。写代码时顺便提一个 Python 新手最容易踩的坑[[0] * (m 1)] * (n 1)看起来生成了 n1 行实际每一行都是同一个列表对象的引用改一行整张表跟着变。必须用列表推导式[[0] * (m 1) for _ in range(n 1)]。4. 手动推演从 kitten 到 sitting4.1 初始化第一行第一列理论再清楚不如拿经典例子“kitten”到“sitting”手推一遍。a kitten长度 6b sitting长度 7。建一张 7 行 8 列的 DP 表行和列都从 0 开始。先填边界。第 0 行从左到右放 0, 1, 2, ..., 7表示空串变成各个前缀只能靠插入。第 0 列从上到下放 0, 1, 2, ..., 6表示各个前缀变成空串只能靠删除。这两条边填好整张表就有了地基。4.2 按行填充并观察数值来源完整推演后的 DP 表如下空sitting空01234567k11234567i22122345t33212345t44321234e55432234n66543323挑两行验证一下。第二行对应 a 的前两个字符“ki”。dp[2][2]是“ki”变“si”的距离最后字符 i 对 i 相等所以直接取dp[1][1] 1也就是“k”变“s”需要一次替换。dp[2][5]是“ki”变“sitti”的距离要从dp[1][5] 1、dp[2][4] 1、dp[1][4] 0三者里取最小最终得到 3。每个格子的来源规律是固定的从上方加一、从左方加一、从左上角加匹配 0 / 不匹配 1三个候选中选最小。手动推一遍之后整个转移方程就不再是抽象公式而是一个有实际意义的填表过程。4.3 从表中如何读出具体编辑序列最终答案在右下角dp[6][7] 3说明 kitten 变成 sitting 最少需要 3 次编辑。一种操作序列是kitten → sitten替换 k 为 s→ sittin替换 e 为 i→ sitting末尾插入 g。从表里可以复现这条路径。看dp[6][7]b 的末尾是 ga 的末尾是 n不相等。dp[6][7]由dp[6][6] 1得到说明这一步是插入 g。dp[6][6]中 a 的 n 与 b 的 n 相等继承dp[5][5]。dp[5][5]中 a 的 e 与 b 的 i 不相等由dp[4][4] 1得到说明替换 e 为 i。继续往回推dp[4][4]的 t 与 t 相等继承dp[3][3]dp[3][3]的 t 与 t 相等继承dp[2][2]dp[2][2]的 i 与 i 相等继承dp[1][1]最后dp[1][1]由dp[0][0] 1得到替换 k 为 s。把这些步骤逆序就得到了上面那三条编辑记录。能靠表反推操作序列说明你真正理解了状态转移。很多面试题不会只要求距离还会问“具体怎么编辑”。后面会有代码来实现这个回溯。5. 代码实现与三种常见形态5.1 标准二维 DP直接可用的基础版本Python 实现非常直白注释都写在代码里def edit_distance(a: str, b: str) - int: n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] # 边界初始化 for i in range(n 1): dp[i][0] i for j in range(m 1): dp[0][j] j for i in range(1, n 1): for j in range(1, m 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 a[i-1] dp[i][j - 1] 1, # 插入 b[j-1] dp[i - 1][j - 1] 1 # 替换 a[i-1] 为 b[j-1] ) return dp[n][m]时间复杂度 O(n × m)空间复杂度也是 O(n × m)。代码里用a[i-1]而不是a[i]是因为 i 代表长度访问的是最后一个字符这个偏移量细节要习惯。跑几个简单用例验证assert edit_distance(, ) 0 assert edit_distance(abc, ) 3 assert edit_distance(, abc) 3 assert edit_distance(cat, dog) 3 assert edit_distance(kitten, sitting) 35.2 滚动数组优化把空间压到一行再看这张表的结构。计算dp[i][j]时只会用到上一整行dp[i-1][:]以及当前行左边的dp[i][j-1]再往前的行以后永远不会被用到。所以没有必要保留完整的二维表用两个一维数组滚动就行。def edit_distance_opt(a: str, b: str) - int: n, m len(a), len(b) prev list(range(m 1)) # 初始化为 dp[0][j] j for i in range(1, n 1): curr [0] * (m 1) curr[0] i # dp[i][0] i for j in range(1, m 1): if a[i - 1] b[j - 1]: curr[j] prev[j - 1] else: curr[j] min(prev[j], curr[j - 1], prev[j - 1]) 1 prev curr return prev[m]空间从 O(n × m) 降到了 O(m)。如果两字符串中比较短的是列甚至可以把 m 定为双方较短长度进一步减少内存。时间还是 O(n × m)没法再降。这里有个换行顺序的细节内层循环跑完一整行之后才能把prev换成curr千万别在循环里提前赋值否则下一个格子的prev[j]已经不是上一行的值了。5.3 回溯实现把路径也一并输出很多情况下你需要的不只是距离还有具体操作步骤。回溯的关键就是记录每个格子是从哪个方向转移来的或者直接在算完后从右下角倒推。下面这份代码不求记录完整路径表而是利用 dp 表倒推最后返回操作列表def edit_distance_with_path(a: str, b: str): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] i for j in range(m 1): dp[0][j] j for i in range(1, n 1): for j in range(1, m 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1 ops [] i, j n, m while i 0 and j 0: if a[i - 1] b[j - 1]: ops.append(f保留 a[{i-1}] {a[i-1]}) i - 1 j - 1 elif dp[i][j] dp[i - 1][j] 1: ops.append(f删除 a[{i-1}] {a[i-1]}) i - 1 elif dp[i][j] dp[i][j - 1] 1: ops.append(f插入 {b[j-1]} 到位置 {i}) j - 1 else: ops.append(f替换 a[{i-1}] {a[i-1]} 为 {b[j-1]}) i - 1 j - 1 # 处理剩余边界 while i 0: ops.append(f删除多余字符 a[{i-1}] {a[i-1]}) i - 1 while j 0: ops.append(f插入剩余字符 {b[j-1]}) j - 1 return dp[n][m], list(reversed(ops))回溯方向要跟转移方向完全对应否则会得到一条“看似合理但成本不是最小”的路径。回溯时优先判断匹配因为匹配状态不会被计入任何 min 分支不匹配时再分别比较三种来源。6. 实际应用场景与工程权衡6.1 搜索提示与拼写纠错搜索引擎里输入错词时系统给出“你是不是想找”的提示背后经常就是编辑距离。不过现实中不会让用户输入一个词就跟整个词典跑一遍 O(n × m)性能顶不住。通常的做法是先建立一个前缀索引或 BK 树把候选词缩小到很小范围再对剩下几十个候选词逐个计算编辑距离。还有一种常见变体叫加权编辑距离。键盘上相邻的字母更容易误触那么替换代价就不再是固定的 1而是根据按键距离设定不同权重。这种扩展只是把转移方程里的常量 1 换成代价函数DP 框架完全不动。6.2 查重和相似度计算论文查重、代码查重本质上是对两份文本做相似度衡量。直接对原始字符串跑编辑距离的问题在于文本长度很大而且单个字符的增删会影响整段内容的距离结果不稳定。工程上一般先把文本切分成句子、子句或 token 序列再对 token 序列计算编辑距离这样每个 token 才是一个有语义的最小单元。计算完距离后通常还会归一化成一个相似度分数比如1 - 距离 / max(len(a), len(b))再用阈值判断是否需要人工复核。这里要特别提醒编辑距离适合判断“相似”不适合判断“包含”。如果只需要判断 B 是否包含在 A 里直接用子串匹配算法会快几个数量级。6.3 生物信息学与序列比对DNA 序列可以看成由 A、T、C、G 四种字符组成的长字符串。两条 DNA 序列的相似度在生物信息学里通常会用更复杂的比对模型但最基础的模型之一就是编辑距离。生物场景里替换代价往往不是 1不同碱基突变概率不同插入和删除也有独立的 gap penalty最终实现不过是把代价换成一个权重矩阵DP 递推方式不变。6.4 什么时候不该硬上编辑距离编辑距离是 O(n × m)当两条文本都是几万甚至几十万字符时直接算会非常慢。如果要处理大规模数据先考虑是不是真的需要精确距离。粗粒度场景可以用 simhash、MinHash 这类指纹算法快速过滤精确匹配则用哈希或索引只有“非常相似但又不完全相同”这个需求确实存在时编辑距离以及它的各种变体才值得上场。7. 高频问题排查与避坑清单7.1 插入和删除的方向总是记反这是最经典的问题。记忆方法可以这么想dp[i][j-1]表示 a 的前 i 个字符已经搞定了 b 的前 j-1 个字符那么 b[j-1] 就是“还缺一个”所以要插入dp[i-1][j]表示 a 的前 i-1 个字符已经搞定了 b 的前 j 个字符那 a[i-1] 就是“多出来一个”所以要删除。拿最简例子“ab”变“b”来验证dp[2][1] 1路径是从 dp[1][1] 删除 a 中的 a 得到的方向就清楚了。7.2 Python 二维列表初始化的隐形坑[[0] * (m 1)] * (n 1)是经典陷阱每一行都是同一个列表对象的引用改任意一行其它行全部同步变化。结果就是 DP 表完全错乱。正确写法是[[0] * (m 1) for _ in range(n 1)]每次生成新列表。检测方法很简单初始化后立刻执行dp[0][0] 99如果所有行的第一列都变成 99就是引用了同一个列表。7.3 空字符串边界没处理好当 a 或 b 为空时答案就是非空字符串的长度。如果初始化时漏了dp[i][0]或dp[0][j]程序会直接越界或给出错误结果。我在 debug 的时候遇到的最多情况就是代码主体没问题边界行和边界列没初始化最终结果差得很离谱。也可能有人喜欢先判断if not a: return len(b) if not b: return len(a)这不算错但只是为了挡空串并不能替代 DP 表里的边界行因为 DP 递推过程中同样会用到 i0 和 j0 的格子。7.4 递归写法到底什么时候会超时很多人顺手就写递归版代码短思路直观但如果不加缓存就会指数爆炸。在递归中同一个子问题会被反复计算n 稍微大一点就会卡死。想保留递归风格就加记忆化from functools import lru_cache def edit_distance_rec(a: str, b: str) - int: lru_cache(None) def dfs(i, j): if i 0: return j if j 0: return i if a[i - 1] b[j - 1]: return dfs(i - 1, j - 1) return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) 1 return dfs(len(a), len(b))加了lru_cache之后状态被限制在 (n1) × (m1) 范围内递归版空间复杂度实际还是 O(n × m)因为缓存表就是这张表。只是 Python 的递归深度有限字符串长度超过 1000 时会触发递归深度限制所以工程代码里我建议直接用迭代版。8. 实操经验与学习心得动态规划这一个系列我练过很多题但回看下来编辑距离是我建议每个人都手推一遍的题。原因在于它非常“直观”三张操作的图片想一想就能画出来一张表推完就能理解所有状态。相比背包问题的各种变体编辑距离的转移几乎完全贴合自然语言的“增删改”直觉。我个人在实际操作中有一个很深的体会学这道题千万不要一上来就背代码。找两个短字符串比如“horse”和“ros”然后拿一张纸从 0,0 开始一个一个格子填。填到第三行的时候你会突然发现状态转移方程不再是天书而是“哦原来每一步就是在选一个最便宜的方向”。这个感觉一旦建立起来后面不管碰到加权编辑距离、支持转置操作的 Damerau-Levenshtein还是需要输出对齐路径的场景都只是在搭好的骨架上改细节。做题和写工程代码其实是两回事。刷题时需要脑内掌握 O(n × m) 复杂度落实到项目里则要先问清楚数据规模。如果你只是处理几千字符的短文本二维数组版直接上代码简单、可读性好。如果是长文本比对那滚动数组是底线再往上还要考虑候选集裁剪、分块并行和阈值提前终止。最后再分享一个调试小技巧写完后先不要用复杂用例测试先用(, )、(a, )、(, a)、(ab, a)这组简单用例跑一遍。这四组能一次性暴露 90% 的初始化问题和下标偏移错误。确认没问题后再用(kitten, sitting) 3这种经典用例验证整体逻辑基本就稳了。字符串的动态规划题很多时候就是在考你能否把一个看似抽象的问题拆成“前缀 最后一次决策”的组合。编辑距离是所有这类题目里最适合入门的一块敲门砖把它彻底吃透下一个遇见的字符串 DP 题你大概率会顺利很多。