编辑距离问题详解：以决策树建模并用动态规划求解——《Hello 算法》Edit Distance Problem 深度解析

编辑距离（Edit Distance，又称 Levenshtein 距离）是信息检索与自然语言处理中度量两个字符串相似度的经典指标，指将一个字符串变换为另一个字符串所需的最少编辑次数。本文以《Hello 算法》英文站 edit_distance_problem.md 为核心骨架，完整还原“决策树建模 → 状态定义 → 最优子结构 → 边界条件 → 代码实现 → 空间优化”的解题全链路，并结合仓库中 15 种语言的可运行源码验证每一处结论。读完你不仅能用动态规划解决编辑距离本身，还能掌握一套从“暴力搜索”到“滚动数组压缩空间”的通用 DP 拆解方法论。

问题定义与运行示例

在深入算法前，先明确问题本身：

!!! question

给定两个字符串 $s$ 和 $t$，返回将 $s$ 转换为 $t$ 所需的最少编辑次数。允许的编辑操作有三种：插入一个字符、删除一个字符、将一个字符替换为任意其他字符。

三个直观例子可以帮助建立感觉：

• 将 kitten 转换为 sitting：把 k 替换为 s、把 e 替换为 i、在末尾插入 g，共 2 次替换 + 1 次插入 = 3 次编辑；
• 将 hello 转换为 algo：删除 h、把 e 替换为 a、把第 2 个 l 替换为 g，共 2 次替换 + 1 次删除 = 3 次编辑。

注意，允许的操作没有顺序与次数上限，因此问题的本质不是“怎么改最直观”，而是在全部可行编辑序列中找最小代价。原文档 edit_distance_problem.md 随后揭示了一个关键视角：这个“找最小代价”的过程可以用决策树模型自然解释。

决策树模型：把编辑过程看成搜索路径

决策树视角下，字符串对应树的节点，每一次编辑操作对应树的一条边。 以 hello 到 algo 为例：根节点是 hello，对它做一次替换、删除或插入会得到各种中间字符串（子节点），对中间字符串继续编辑又会分支出更多子节点。由于操作不受限制，每个节点可以分出许多分支，因此在整棵决策树中，从 hello 出发的可行路径数量非常大。

于是原问题被等价改写为一个图上的最短路问题：

在决策树中，找出从节点 hello 到节点 algo 的最短路径。

“路径长度”即编辑次数。这个改写意义重大——它把原来难以直接度量的字符串变换问题，变成了一个具有清晰结构与递推关系的组合优化问题，为下一步“把问题规模逐步缩小、构造子问题”铺平了道路。

动态规划求解四步法

决策树完整展开会指数级爆炸，因此需要动态规划剪枝。下面严格遵循原文档的三步推导框架，并补上复杂度分析。

Step 1：定义状态，得到 dp 表

要让问题规模在编辑过程中逐渐缩小，核心技巧是从两个字符串的尾部字符开始考虑。设 $s$、$t$ 的长度分别为 $n$、$m$，考察尾字符 $s[n-1]$ 与 $t[m-1]$：

• 若两者相同，可直接“跳过”，转而去比较 $s[n-2]$ 与 $t[m-2]$；
• 若两者不同，则必须对 $s$ 执行一次编辑（插入 / 删除 / 替换），使尾部对齐后再进入更小规模的问题。

因此每一轮决策都会改变 $s$ 和 $t$ 中尚未匹配的字符范围，状态自然被定义为 $s$ 中当前考虑的前 $i$ 个字符与 $t$ 中当前考虑的前 $j$ 个字符，记作 $[i, j]$。

状态 $[i, j]$ 对应子问题：将 $s$ 的前 $i$ 个字符变为 $t$ 的前 $j$ 个字符所需的最少编辑次数。

由此得到一个大小为 $(n+1) \times (m+1)$ 的二维 $dp$ 表。多出的“+1”行与列，是为了容纳“某字符串为空”的边界情形。

Step 2：最优子结构与状态转移方程

考察子问题 $dp[i, j]$，其对应的尾字符是 $s[i-1]$ 与 $t[j-1]$。当二者不同时，三种编辑操作分别把问题导向三个更小的子问题：

当前操作	操作描述	剩余子问题
插入	在 $s[i-1]$ 之后插入 $t[j-1]$	$dp[i, j-1]$
删除	删除 $s[i-1]$	$dp[i-1, j]$
替换	将 $s[i-1]$ 替换为 $t[j-1]$	$dp[i-1, j-1]$

由此得到最优子结构：$dp[i, j]$ 的最少编辑次数，等于左侧、上方、左上三个子问题的最小值，再加上当前这次编辑的代价 $1$：

$$dp[i, j] = \min(dp[i, j-1],\ dp[i-1, j],\ dp[i-1, j-1]) + 1$$

特别注意特例：当 $s[i-1]$ 与 $t[j-1]$ 相同时，当前字符无需任何编辑，直接继承左上角结果：

$$dp[i, j] = dp[i-1, j-1]$$

这个“相等即继承、不相等才加一”的写法，是全文最容易写错的地方——很多人会忘记判断相等分支，导致答案系统性偏大。

Step 3：边界条件与遍历顺序

• 两串皆空：$dp[0, 0] = 0$；
• $s$ 空、$t$ 非空：只能逐字符插入，故首行 $dp[0, j] = j$；
• $s$ 非空、$t$ 空：只能逐字符删除，故首列 $dp[i, 0] = i$。

观察转移方程可知，$dp[i, j]$ 依赖左方 $dp[i, j-1]$、上方 $dp[i-1, j]$、左上 $dp[i-1, j-1]$ 三个状态，因此只要用两个嵌套循环按行优先、从左到右、从上到下填表即可保证每个格子计算前依赖项已就绪。

复杂度：主循环共 $n \times m$ 个格子，每格 O(1) 求值，故时间复杂度为 $O(nm)$；二维表占用 $O(nm)$ 空间（空间优化后降为 $O(m)$，见后文）。

代码实现：从暴力搜索到记忆化再到 DP

仓库中本主题的完整可运行代码位于 codes/*/chapter_dynamic_programming/edit_distance.*，覆盖 Python、Java、C++、C、C#、Go、Swift、Rust、Ruby、Kotlin、TypeScript、JavaScript、Dart、Zig 等主流语言。以英文版 edit_distance.py 为例，源码中实际实现了四条递进路线，与文档正文的 edit_distance_dp / edit_distance_dp_comp 相互印证：

（1）暴力搜索 edit_distance_dfs——严格照搬递推式，无任何缓存，验证“朴素递归会指数爆炸”：

def edit_distance_dfs(s: str, t: str, i: int, j: int) -> int:
    if i == 0 and j == 0:
        return 0
    if i == 0:
        return j
    if j == 0:
        return i
    if s[i - 1] == t[j - 1]:
        return edit_distance_dfs(s, t, i - 1, j - 1)
    insert = edit_distance_dfs(s, t, i, j - 1)
    delete = edit_distance_dfs(s, t, i - 1, j)
    replace = edit_distance_dfs(s, t, i - 1, j - 1)
    return min(insert, delete, replace) + 1

（2）记忆化搜索 edit_distance_dfs_mem——用 mem 表（初值 -1）缓存重叠子问题，代码结构与暴力版一一对应，但把指数时间压缩到 $O(nm)$。从源码结构看，它与“暴力搜索 → 记忆化 → 动态规划”的经典教学序列完全一致。

（3）二维 DP edit_distance_dp——文档正文引用的核心函数，先用循环初始化首行首列，再逐格填表：

def edit_distance_dp(s: str, t: str) -> int:
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    return dp[n][m]

原文档同时指出：编辑距离的填表过程与 0-1 背包问题高度相似，本质都是逐格填充二维网格。文档的 step1 ~ step15 示意图（位于 edit_distance_problem.assets 目录，文件名如 edit_distance_dp_step1.png）完整演示了整张表从左上角到右下角的逐格推进过程，建议配合下面的状态转移文字逐帧对照阅读。

运行验证

仓库各语言源码均在文件末尾带有驱动代码。以 Python 为例，在 codes/python/chapter_dynamic_programming 目录执行：

python edit_distance.py

驱动代码将 s = "bag"、t = "pack" 同时送入暴力搜索、记忆化搜索、二维 DP、空间优化 DP 四种实现并打印结果，四种方法输出一致（最少 3 步），可直接用于交叉验证算法正确性。Java 版驱动代码见 edit_distance.java，其 main 方法体与 Python 版逐行对应。

空间优化：用 leftup 变量把二维表压成一维

原文档指出一个经典“坑”：

由于 $dp[i, j]$ 依赖上方 $dp[i-1, j]$、左方 $dp[i, j-1]$ 与左上 $dp[i-1, j-1]$ 三个状态：正向遍历会丢失左上状态，反向遍历又无法先构造出左方状态，所以两种滚动数组的常规遍历顺序都不适用。

解法是引入一个临时变量 leftup 专门暂存左上角 $dp[i-1,j-1]$，让一维数组只需同时关心“左方”和“上方”两个值即可——这与完全背包问题的空间优化手法如出一辙（可对照 unbounded_knapsack_problem.md）。优化后空间复杂度从 $O(nm)$ 降至 $O(m)$：

def edit_distance_dp_comp(s: str, t: str) -> int:
    n, m = len(s), len(t)
    dp = [0] * (m + 1)
    for j in range(1, m + 1):
        dp[j] = j
    for i in range(1, n + 1):
        leftup = dp[0]   # 暂存 dp[i-1][j-1]
        dp[0] += 1       # 相当于二维写法中的首列初始化 dp[i][0] = i
        for j in range(1, m + 1):
            temp = dp[j]
            if s[i - 1] == t[j - 1]:
                dp[j] = leftup
            else:
                dp[j] = min(dp[j - 1], dp[j], leftup) + 1
            leftup = temp  # 更新为下一轮的 dp[i-1][j-1]
    return dp[m]

逐行拆解这段代码，可以看到三个关键细节：

1. 处理第 $i$ 行前，先把 dp[0] 备份进 leftup，它就是上一轮（第 $i-1$ 行）的 dp[0]，即二维表中的 $dp[i-1][0]$；
2. 内层循环里 temp = dp[j] 先保存当前行旧值，随后 leftup = temp 完成“向右下对角移动”的接力，保证每列计算时 leftup 恰好还是 $dp[i-1][j-1]$；
3. 正因为依赖项只剩“本行左侧 + 上一行本列 + leftup”，采用正向遍历即可安全覆盖，这正是文档所说“此情形与完全背包相同，可使用正向遍历”的代码落地。

对比 edit_distance.py 中 edit_distance_dp 与 edit_distance_dp_comp 两个函数会发现：二维版把“首行首列初始化”放在主循环外显式完成，而压缩版把首列初始化融入每轮 dp[0] += 1，两种写法在语义上完全等价，可作为阅读其他语言版本时的对照锚点。

多语言实现一览与延伸阅读

本主题在仓库根目录 codes 与英文目录 en/codes 下均有完整镜像，核心文件统一命名为 edit_distance，便于跨语言对照：

语言	源码位置（英文镜像同名同构）
Python	codes/python/chapter_dynamic_programming/edit_distance.py
Java	codes/java/chapter_dynamic_programming/edit_distance.java
C++	codes/cpp/chapter_dynamic_programming/edit_distance.cpp
Go	codes/go/chapter_dynamic_programming/edit_distance.go
C / C# / Swift / Rust / Ruby / Kotlin / TS / JS / Dart / Zig	同路径 codes/<语言>/chapter_dynamic_programming/edit_distance.*

跨语言对照时可留意三点实现差异：一是字符串索引方式（C/C++/Go 用 s[i-1] 下标，Java/Kotlin 用 charAt(i-1)，Python/Ruby 用切片语义）；二是 C++/C 对“删除”操作的命名习惯使用 del 而非 delete（避免关键字冲突，见 edit_distance.cpp）；三是内存表初始化方式（Java 用 Arrays.fill(row, -1)，Go 用切片字面量构建）。以上语言文件均可直接编译运行，用于验证算法在不同运行时下行为一致。

针对可视化学习需求，仓库还提供 PythonTutor 逐步执行版 edit_distance.md，可将递归/DP 过程逐步可视化。

想继续深入本主题所在的动态规划章节，推荐按以下顺序阅读同目录文档：

• knapsack_problem.md：编辑距离“填二维表”的结构与 0-1 背包同源，先理解背包即掌握了大半；
• unbounded_knapsack_problem.md：leftup 一维压缩技巧的姊妹案例；
• dp_solution_pipeline.md：从“定义状态 → 推导转移 → 边界与顺序 → 空间优化”的整体方法论，本文即其完整范本；
• dp_problem_features.md：判断“最优子结构 + 无后效性”两大 DP 适用条件的理论依据。

小结

编辑距离问题的完整解题链条可以浓缩为一句话：用尾部字符对齐不断缩小问题规模，用“插入/删除/替换”三种操作枚举所有转移，用 $dp[i][j] = \min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1$（字符相同时直接取 $dp[i-1][j-1]$）完成状态递推，最后用 leftup 变量把空间压到 $O(m)$。

掌握这个案例后，你会获得三个可迁移的能力：其一是“从决策树/搜索视角切入再转 DP”的建模直觉；其二是对 相等跳过 / 不等取三路最小值加一 这类分支状态转移的敏感度（后续可延伸到最长公共子序列等姊妹问题）；其三是一维滚动数组在“三方向依赖”时的 leftup 处理技巧。仓库中 15 种语言的 edit_distance 实现与 17 张过程示意图 可以随时取用，作为学习或面试前复习的第一手资料。