专题进阶 · 动态规划推荐总顺序 · 第 71 / 148 课

按最后一次编辑操作分类,区别删除、插入和替换对应的前缀变化。

先学会这些,再进入本课 最长公共子序列 二维 DP
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

编辑距离Edit Distance

用插入、删除、替换三种最后操作建立二维最小代价转移。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

按最后一次编辑操作分类,区别删除、插入和替换对应的前缀变化。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

把 'cat' 改成 'cut',允许每次插入、删除或替换一个字符,求最少操作数。

02一步步得到方法

定义变换方向

dp[i][j] 表示把 a 的前 i 个字符变为 b 的前 j 个字符的最小成本。a 为空时需要插入 j 次;b 为空时需要删除 i 次,因此首行首列分别是 0..m、0..n。

若末尾相等,可以直接保留,代价来自左上。若不等,最后一步可能是删除 a 的末尾,对应 dp[i−1][j]+1;插入 b 的末尾,对应 dp[i][j−1]+1;替换,对应 dp[i−1][j−1]+1。

不要只比较同一位置的字符

插入和删除会改变后续对齐关系。例如 abc→zabc 只需一次插入,而逐位置比较会误认为很多字符都不同。二维状态正是保存不同前缀对齐的方式。

本课单位代价 Levenshtein 距离不包含相邻交换。若题目允许交换,需新增合法操作及依赖,不能声称当前代码已经覆盖。

三个操作对应三个前缀状态

从短前缀到长前缀,删除消耗源字符,插入消耗目标字符,替换同时消耗两边字符。因此三个邻居分别代表不同的剩余编辑任务,不是任意挑三个方向。

若字符相同可零成本对齐,若不同再加替换成本。操作权重不同时公式要显式使用各权重;相邻交换也不是普通 Levenshtein 距离已有的操作,需要扩展模型。

03把一个小例子完全算清楚

a='cat',b='cut'。

步骤计算与状态为什么这样做
空行[0,1,2,3]逐个插入目标前缀
c 行[1,0,1,2]c 与 c 可保留
ca 行[2,1,1,2]a→u 替换一次
cat 行[3,2,2,1]最后 t 保留

窄屏可左右滑动表格,阅读完整计算与理由。

距离为 1;表格同时比较不同长度的前缀,自动寻找最佳对齐。

04为什么这个方法成立

  1. 空前缀边界是唯一必要的插入或删除数量。
  2. 任一最优编辑序列的最后一步属于保留、插入、删除、替换之一。
  3. 相应更短前缀若不是最优,可替换为更优方案,故取候选最小值正确。

05把推导翻译成代码

Python · 可独立运行的教学实现

def edit_distance(a,b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1): dp[i][0] = i
    for j in range(len(b)+1): dp[0][j] = j
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            replace = dp[i-1][j-1] + (a[i-1] != b[j-1])
            dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,replace)
    return dp[-1][-1]

逐个理解关键决定

(a[i-1] != b[j-1])
相等时代价 0,不相等时代价 1,统一保留与替换。
dp[i][0] = i
不能把整表边界都初始化为零,否则删除成本被忽略。

06时间、空间与实现范围

时间 O(nm),完整表空间 O(nm);只求距离可保存两行。

文本按 Python 码点处理,用户可见字符层面的编辑距离需要先做字素簇分段。

07改变条件,检查哪里会出错

把 LCS 公式直接当作包含替换的距离

cat→cut 可替换一次,删除再插入要两次,两种操作集合不同。

空串边界全部设为0

空串变为长度 j 的目标需 j 次插入,反向需 i 次删除,边界必须表达这些真实成本。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

空串到 'abc' 距离多少?

需要一点提示

只能插入。

查看解析与答案

3。

练习 2 · 边界与辨析

'ab'→'ba' 本课距离多少?

需要一点提示

没有交换操作。

查看解析与答案

2,可替换两次;不能按一次相邻交换计算。

练习 3 · 变式与迁移

删除代价 2、插入 1、替换 3 怎么改?

需要一点提示

同时修改转移与边界。

查看解析与答案

首列 2i、首行 j,三条候选分别加 2、1、3,相等保留仍为 0。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。