Hello 算法：编辑距离问题的动态规划详解与多语言代码实现

编辑距离（Levenshtein 距离）是度量两个字符串相似度的经典算法，广泛应用于信息检索、拼写纠错与自然语言处理。本文基于《Hello 算法》仓库中 编辑距离问题文档 展开，完整讲解如何从决策树模型出发，经过"定义状态、推导转移方程、确定边界条件"三步建立动态规划模型，并深入剖析仓库中 Python、Java、C++ 等实现里"二维 dp 表"与"空间优化"两种版本的核心代码差异。读完本文，你将能够独立推导编辑距离的状态转移方程，并理解一维滚动数组 + leftup 变量这一经典空间优化技巧的来龙去脉。

一、问题定义与编辑操作

编辑距离指两个字符串之间互相转换的最少修改次数。问题描述如下：

• 输入两个字符串 s 和 t，返回将 s 转换为 t 所需的最少编辑步数；
• 允许三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符，每次操作记 1 步。

仓库文档给出的两个直观例子：

源串	目标串	最少步数	操作构成
kitten	sitting	3	2 次替换 + 1 次添加
hello	algo	3	2 次替换 + 1 次删除

而仓库各语言代码中的标准测试用例是 s = "bag"、t = "pack"：最少编辑步数为 3（例如 b → p 替换、g → c 替换、末尾插入 k）。该用例在 Go 测试文件 中被同时用于驱动暴力搜索、记忆化搜索、动态规划与空间优化四个版本的函数。

二、决策树模型：把编辑操作看成最短路径

编辑距离问题可以很自然地用决策树模型来解释：字符串对应树节点，一轮决策（一次编辑操作）对应树的一条边。

在不限制操作的情况下，每个节点都可以派生出许多条边——每个字符位置都能插入任意字符、删除当前字符或替换为任意字符，因此从 hello 转换到 algo 存在大量可能的路径。从决策树角度看，本题的目标就是求解节点 hello 与节点 algo 之间的最短路径。

直接搜索决策树会产生指数级爆炸，这正是需要用动态规划消除子问题重叠的动机。仓库的 Python 实现 中保留了这一朴素版本 edit_distance_dfs：三个分支分别对应插入 (i, j-1)、删除 (i-1, j)、替换 (i-1, j-1)，返回 min(insert, delete, replace) + 1；其记忆化版本 edit_distance_dfs_mem（第 30-53 行）则用 mem 表避免重复计算。这两个版本与下文 DP 版本共用同一套边界条件：

• i == 0 and j == 0：两串都为空，返回 0；
• i == 0：s 为空，需全部插入，返回 j；
• j == 0：t 为空，需全部删除，返回 i。

三、动态规划三步法

第一步：思考每轮决策，定义状态

每一轮的决策是对字符串 s 进行一次编辑操作。为了让问题规模逐渐缩小，我们从两字符串尾部的字符 s[n-1] 与 t[m-1] 入手（设 s、t 长度分别为 n、m）：

• 若 s[n-1] 和 t[m-1] 相同，可以跳过它们，直接考虑 s[n-2] 和 t[m-2]；
• 若不同，需要对 s 进行一次编辑（插入、删除、替换），使尾部字符相同后再跳过它们，考虑规模更小的问题。

也就是说，在 s 中进行的每一轮编辑都会改变两串中"剩余待匹配字符"的边界。因此状态取为当前在 s 和 t 中考虑的第 i 个和第 j 个字符，记为 [i, j]。状态 [i, j] 对应的子问题是：将 s 的前 i 个字符更改为 t 的前 j 个字符所需的最少编辑步数。

由此得到一张尺寸为 (n+1) × (m+1) 的二维 dp 表——多出来的首行首列恰好容纳"某串为空"的边界情况。

第二步：最优子结构与状态转移方程

考虑子问题 dp[i, j]，两个字符串的尾部字符为 s[i-1] 和 t[j-1]，按编辑操作分为三种情况：

1. 在 s[i-1] 之后添加 t[j-1]（插入），剩余子问题 dp[i, j-1]；
2. 删除 s[i-1]，剩余子问题 dp[i-1, j]；
3. 将 s[i-1] 替换为 t[j-1]，剩余子问题 dp[i-1, j-1]。

于是得到最优子结构：dp[i, j] 的最少编辑步数等于 dp[i, j-1]、dp[i-1, j]、dp[i-1, j-1] 三者中的最少编辑步数，再加上本次编辑步数 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]

这一分支正是 Python 实现第 68-70 行 中 if s[i-1] == t[j-1] 的判断，它在字符匹配时省去了 +1 的代价。

第三步：边界条件与遍历顺序

• 两字符串都为空时编辑步数为 0，即 dp[0, 0] = 0；
• s 为空但 t 不为空时，最少编辑步数等于 t 的长度，即首行 dp[0, j] = j；
• s 不为空但 t 为空时，最少编辑步数等于 s 的长度，即首列 dp[i, 0] = i。

观察状态转移方程，解 dp[i, j] 依赖左方、上方、左上方的解，因此用两层循环正序遍历整个 dp 表即可——这与 文档中的背包问题填表动画 呈现的过程非常相似，都是从首行首列逐格推进。

四、代码实现：二维 dp 表版本

以下是 Python 实现 中的 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:
                # 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    return dp[n][m]

代码结构可以逐行对照前文的三步法：前两个 for 循环填首列首行（边界条件），双重循环内部先判断字符是否相等，再走对应转移方程。各语言实现的逻辑完全一致，可对照阅读：

• Java：editDistanceDP，用 Math.min(Math.min(...), ...) 实现三元取小；
• C++：editDistanceDP，dp 以 vector<vector<int>> 存储；
• Go 的 测试用例 中以 bag / pack 验证 editDistanceDP 输出 3。

此外，仓库为本文代码提供了 Pythontutor 在线可视化入口，可以逐指令单步查看 edit_distance_dp 与空间优化版 edit_distance_dp_comp 的变量变化过程。

五、空间优化：一维数组与 leftup 变量

二维表的空间复杂度为 O((n+1)(m+1))，但可以进一步压缩。文档指出了两个常见误区：

• dp[i, j] 由上方 dp[i-1, j]、左方 dp[i, j-1]、左上方 dp[i-1, j-1] 转移而来，正序遍历会丢失左上方的旧值（它先被当前行覆盖）；
• 倒序遍历无法提前构建 dp[i, j-1]（左方是当行更小的列，倒序时还未计算）。

因此两种简单的遍历顺序调整都不可取。正确做法是用一个变量 leftup 暂存左上方的解 dp[i-1, j-1]，从而只需考虑左方和上方的解；这与完全背包问题的处理相同，可以继续使用正序遍历。

空间优化版本 edit_distance_dp_comp 的关键细节如下：

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
        # 状态转移：其余列
        for j in range(1, m + 1):
            temp = dp[j]
            if s[i - 1] == t[j - 1]:
                # 若两字符相等，则直接跳过此两字符
                dp[j] = leftup
            else:
                # 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[j] = min(dp[j - 1], dp[j], leftup) + 1
            leftup = temp  # 更新为下一轮的 dp[i-1, j-1]
    return dp[m]

从源码结构看，这段代码有三个值得注意的映射关系：

1. 左方解：dp[j-1] 是上一轮循环刚写好的当行值；
2. 上方解：dp[j] 是尚未被当前行覆盖的上一行旧值；
3. 左上方解：leftup。每列循环末尾执行 leftup = temp，把"本列覆盖前的旧值"滚动保存为下一列所需的 dp[i-1, j-1]；

首列的维护也遵循同一逻辑：进入新行时先 leftup = dp[0] 保存旧首列值，再 dp[0] += 1 令其变为 i（即边界条件 dp[i, 0] = i）。Java 版本 editDistanceDPComp 中 dp[0] = i 的写法与 Python 的 dp[0] += 1 等价，只是表达形式不同。优化后空间复杂度降为 O(m+1)（若交换 s/t 角色，可进一步取两者中较短者作为列数）。

六、运行验证与复杂度小结

各语言文件都内置了可独立运行的驱动代码。以 Python 文件 的 Driver Code 为例，四个版本都以 s = "bag"、t = "pack" 为输入并打印结果：

python codes/python/chapter_dynamic_programming/edit_distance.py

四个版本均输出：

将 bag 更改为 pack 最少需要编辑 3 步

Go 语言可直接用 go test 触发同一组用例（见 edit_distance_test.go）。复杂度方面，二维表版本时间复杂度为 O(nm)，空间复杂度为 O(nm)；空间优化版时间不变，空间降为 O(min(n, m)) 量级。

实现版本	对应函数	时间复杂度	空间复杂度
暴力搜索	edit_distance_dfs	指数级（大量重复子问题）	O(n) 递归栈
记忆化搜索	edit_distance_dfs_mem	O(nm)	O(nm)
动态规划	edit_distance_dp	O(nm)	O(nm)
空间优化	edit_distance_dp_comp	O(nm)	O(m)

编辑距离是"填二维网格"类 DP 问题的典型代表：状态取"两串各自已处理的前缀长度"，转移围绕三种编辑操作展开，边界由"空串"情形给出，最后用滚动数组压缩空间。掌握这套推导与优化套路后，迁移到其他序列对齐问题（如文档同章的 dp 问题特征 与 dp 解题流程 所归纳的方法）会顺畅许多。