Hello 算法编辑距离Levenshtein 距离动态规划详解与空间优化实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo编辑距离Edit Distance又称莱文斯坦距离Levenshtein Distance用于量化两个字符串之间的相似程度是信息检索与自然语言处理领域的经典度量指标。本文以《Hello 算法》仓库中俄文版 edit_distance_problem.md 为核心骨架结合仓库内 Python、Java、C、Go、JavaScript 等多语言实现源码系统讲解从暴力搜索、记忆化搜索到二维动态规划、一维空间优化的完整推导路径。读完本文你将掌握编辑距离的状态定义、状态转移方程推导与空间压缩技巧并能在实际项目中直接复用仓库提供的 edit_distance.py 等现成实现。问题定义与决策树模型问题描述给定两个字符串s和t返回将s转换为t所需的最少编辑步数。对字符串允许三种编辑操作插入在任意位置插入一个字符删除删除任意一个字符替换将一个字符替换为任意其他字符。例如将kitten转换为sitting需要 3 步编辑2 次替换 1 次插入将hello转换为algo也需要 3 步2 次替换 1 次删除。原文示例图清晰展示了这两组转换路径。用决策树解释编辑距离编辑距离问题可以自然映射为决策树模型字符串对应决策树的节点一步决策即一次编辑操作对应树中的一条边每个节点在操作数不限的情况下可以延伸出多条边每条边代表一种转换方案因此hello到algo存在多种不同转换路径问题的目标即转化为在决策树中寻找hello节点到algo节点的最短路径。决策树视角揭示了问题的两大难点一是搜索空间巨大穷举所有路径是指数级二是大量路径共享相同的前缀子问题即存在重叠子问题。这正是动态规划能够显著加速的根本原因。动态规划三步骤推导第一步设计状态确定 dp 表每一轮决策是对字符串s执行一次编辑操作。为了让问题规模逐步缩小从而构建子问题设s与t的长度分别为n和m先观察两串的最后一个字符s[n-1]与t[m-1]若s[n-1] t[m-1]两字符匹配可以直接跳过转而比较s[n-2]与t[m-2]若s[n-1] ! t[m-1]需要对s执行一次编辑操作插入、删除或替换使末位字符相同然后转入规模更小的子问题。因此状态由s与t中当前待比较字符的位置决定记作状态[i, j]。其对应子问题为将s的前i个字符转换为t的前j个字符所需的最少编辑次数。由此得到尺寸为(n1) × (m1)的二维 dp 表dp[i][j]即状态[i, j]的最优值。第二步寻找最优子结构推导状态转移方程考虑子问题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]### 第三步确定边界条件与遍历顺序 - 两串皆为空时编辑次数为 0即 dp[0][0] 0 - s 为空、t 非空时最小编辑次数等于 t 的长度**首行**初始化为 dp[0][j] j - s 非空、t 为空时最小编辑次数等于 s 的长度**首列**初始化为 dp[i][0] i。 由转移方程可知dp[i, j] 只依赖**左方** dp[i, j-1]、**上方** dp[i-1, j] 与**左上** dp[i-1, j-1] 三个值因此可用两层正序循环自底向上填满整张 dp 表。原文档以 15 张逐步示意图[edit_distance_dp_step1.png](https://link.gitcode.com/i/ccca3b84f3b914cf38500937842d0881) 至 [edit_distance_dp_step15.png](https://link.gitcode.com/i/f14b7b8a78aa4778aa559e9b0913c0d3)完整演示了填表全过程其模式与背包问题的二维网格填充高度相似。 ## 源码级实现从暴力搜索到动态规划 仓库中该问题共提供四个递进版本的实现均可在各语言的 chapter_dynamic_programming/edit_distance.* 中找到如 [edit_distance.py](https://link.gitcode.com/i/8974584e5fab113ba6657cd6dfadc154)、[edit_distance.java](https://link.gitcode.com/i/d3c16c028e6027fc1b7215c67acf831c)、[edit_distance.cpp](https://link.gitcode.com/i/1db9fbf63d451538bf7eed4803bd166f)、[edit_distance.go](https://link.gitcode.com/i/9b14c7f5ee1f6a182738a4fa249a3a62)、[edit_distance.js](https://link.gitcode.com/i/b718a4c123ad7703f573b09d9f7dc1a2)。 ### 版本一暴力搜索递归穷举 python def edit_distance_dfs(s: str, t: str, i: int, j: int) - int: 编辑距离暴力搜索 # 若 s 和 t 都为空则返回 0 if i 0 and j 0: return 0 # 若 s 为空则返回 t 长度 if i 0: return j # 若 t 为空则返回 s 长度 if j 0: return i # 若两字符相等则直接跳过此两字符 if s[i - 1] t[j - 1]: return edit_distance_dfs(s, t, i - 1, j - 1) # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 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暴力搜索直接对应决策树模型代码忠实还原了三种操作的递归分支。其递归树中存在大量重叠子问题时间复杂度为指数级仅适合作为推导基准。版本二记忆化搜索def edit_distance_dfs_mem(s: str, t: str, mem: list[list[int]], i: int, j: int) - int: 编辑距离记忆化搜索 # 若 s 和 t 都为空则返回 0 if i 0 and j 0: return 0 # 若 s 为空则返回 t 长度 if i 0: return j # 若 t 为空则返回 s 长度 if j 0: return i # 若已有记录则直接返回之 if mem[i][j] ! -1: return mem[i][j] # 若两字符相等则直接跳过此两字符 if s[i - 1] t[j - 1]: return edit_distance_dfs_mem(s, t, mem, i - 1, j - 1) # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 insert edit_distance_dfs_mem(s, t, mem, i, j - 1) delete edit_distance_dfs_mem(s, t, mem, i - 1, j) replace edit_distance_dfs_mem(s, t, mem, i - 1, j - 1) # 记录并返回最少编辑步数 mem[i][j] min(insert, delete, replace) 1 return mem[i][j]与暴力搜索的唯一差别在于引入mem[i][j] ! -1的查表短路保证每个重叠子问题只计算一次。该版本本质是自顶向下的递归写法时间复杂度降为O(nm)。版本三二维 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]该实现严格遵循前三步推导先初始化首行首列边界条件再以正序双层循环填充内部单元格转移方程最终返回dp[n][m]。时间复杂度和空间复杂度均为O(nm)。仓库中 Java、C、Go、JS 等语言版本结构与之一致例如 edit_distance.java 中editDistanceDP函数用Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) 1实现同一转移逻辑。空间优化用 leftup 变量突破遍历顺序限制二维 dp 表能否压缩为一维关键在于转移依赖关系dp[i, j]依赖上方dp[i-1, j]、左方dp[i, j-1]、左上dp[i-1, j-1]若沿用正序遍历dp[i-1][j-1]已被本轮覆盖丢失左上方旧值若改为逆序遍历又无法预先得到左方新值dp[i, j-1]。因此两种朴素的一维遍历策略在此均不适用这与 0-1 背包、完全背包的优化情形不同。解法引入临时变量leftup在覆盖前保存左上角值dp[i-1, j-1]。此后只需考虑上方与左方两个值局面就等价于完全背包问题可以放心使用正序遍历。仓库实现如下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]关键执行顺序需要仔细理解每行开始前leftup dp[0]暂存上一行首列值随后dp[0] 1表示本行首列dp[i][0] i内层循环中先temp dp[j]记录当前即上一行j列值计算完dp[j]后将leftup更新为temp从而在下一列j1时leftup恰好等于dp[i-1][j]即下一个单元格的左上方旧值字符相等时直接dp[j] leftup不等时min(dp[j-1], dp[j], leftup) 1对应左、上、左上三个来源。优化后空间复杂度从O(nm)降至O(m)时间复杂度保持O(nm)不变。C 版本 edit_distance.cpp 中editDistanceDPComp、Go 版本 edit_distance.go 中editDistanceDPComp均采用完全相同的leftUp暂存策略可对照阅读不同语言的同构实现。运行验证与结果仓库各语言文件末尾均附带 Driver Code统一以s bag、t pack作为测试用例依次调用暴力搜索、记忆化搜索、二维 dp 与空间优化版本并打印结果例如 edit_distance.py 中的驱动代码if __name__ __main__: s bag t pack n, m len(s), len(t) # 暴力搜索 res edit_distance_dfs(s, t, n, m) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 记忆化搜索 mem [[-1] * (m 1) for _ in range(n 1)] res edit_distance_dfs_mem(s, t, mem, n, m) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 动态规划 res edit_distance_dp(s, t) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 空间优化后的动态规划 res edit_distance_dp_comp(s, t) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步)四个版本对bag → pack均输出最少 4 步编辑互相印证了算法正确性。读者可在任意语言目录下直接运行对应文件验证例如python codes/python/chapter_dynamic_programming/edit_distance.py也可参考 edit_distance_test.go 中的测试写法。总结要点编辑距离莱文斯坦距离衡量两字符串相似度允许插入、删除、替换三种操作答案为最少编辑步数状态定义为dp[i][j]将s前i个字符转换为t前j个字符的最少步数dp 表尺寸(n1) × (m1)转移方程字符相等时dp[i][j] dp[i-1][j-1]不等时dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) 1边界dp[0][0] 0、首行dp[0][j] j、首列dp[i][0] i空间优化时因依赖左、上、左上三值正序与逆序单独使用均不可行须借助leftup变量暂存左上值后再正序遍历空间复杂度由O(nm)降至O(m)完整的多语言实现与逐步图解均在仓库中文档位于 ru/docs/chapter_dynamic_programming/edit_distance_problem.md代码位于各语言codes/*/chapter_dynamic_programming/edit_distance.*可对照学习。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法：编辑距离（Levenshtein 距离）动态规划详解与空间优化实战
Hello 算法编辑距离Levenshtein 距离动态规划详解与空间优化实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo编辑距离Edit Distance又称莱文斯坦距离Levenshtein Distance用于量化两个字符串之间的相似程度是信息检索与自然语言处理领域的经典度量指标。本文以《Hello 算法》仓库中俄文版 edit_distance_problem.md 为核心骨架结合仓库内 Python、Java、C、Go、JavaScript 等多语言实现源码系统讲解从暴力搜索、记忆化搜索到二维动态规划、一维空间优化的完整推导路径。读完本文你将掌握编辑距离的状态定义、状态转移方程推导与空间压缩技巧并能在实际项目中直接复用仓库提供的 edit_distance.py 等现成实现。问题定义与决策树模型问题描述给定两个字符串s和t返回将s转换为t所需的最少编辑步数。对字符串允许三种编辑操作插入在任意位置插入一个字符删除删除任意一个字符替换将一个字符替换为任意其他字符。例如将kitten转换为sitting需要 3 步编辑2 次替换 1 次插入将hello转换为algo也需要 3 步2 次替换 1 次删除。原文示例图清晰展示了这两组转换路径。用决策树解释编辑距离编辑距离问题可以自然映射为决策树模型字符串对应决策树的节点一步决策即一次编辑操作对应树中的一条边每个节点在操作数不限的情况下可以延伸出多条边每条边代表一种转换方案因此hello到algo存在多种不同转换路径问题的目标即转化为在决策树中寻找hello节点到algo节点的最短路径。决策树视角揭示了问题的两大难点一是搜索空间巨大穷举所有路径是指数级二是大量路径共享相同的前缀子问题即存在重叠子问题。这正是动态规划能够显著加速的根本原因。动态规划三步骤推导第一步设计状态确定 dp 表每一轮决策是对字符串s执行一次编辑操作。为了让问题规模逐步缩小从而构建子问题设s与t的长度分别为n和m先观察两串的最后一个字符s[n-1]与t[m-1]若s[n-1] t[m-1]两字符匹配可以直接跳过转而比较s[n-2]与t[m-2]若s[n-1] ! t[m-1]需要对s执行一次编辑操作插入、删除或替换使末位字符相同然后转入规模更小的子问题。因此状态由s与t中当前待比较字符的位置决定记作状态[i, j]。其对应子问题为将s的前i个字符转换为t的前j个字符所需的最少编辑次数。由此得到尺寸为(n1) × (m1)的二维 dp 表dp[i][j]即状态[i, j]的最优值。第二步寻找最优子结构推导状态转移方程考虑子问题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]### 第三步确定边界条件与遍历顺序 - 两串皆为空时编辑次数为 0即 dp[0][0] 0 - s 为空、t 非空时最小编辑次数等于 t 的长度**首行**初始化为 dp[0][j] j - s 非空、t 为空时最小编辑次数等于 s 的长度**首列**初始化为 dp[i][0] i。 由转移方程可知dp[i, j] 只依赖**左方** dp[i, j-1]、**上方** dp[i-1, j] 与**左上** dp[i-1, j-1] 三个值因此可用两层正序循环自底向上填满整张 dp 表。原文档以 15 张逐步示意图[edit_distance_dp_step1.png](https://link.gitcode.com/i/ccca3b84f3b914cf38500937842d0881) 至 [edit_distance_dp_step15.png](https://link.gitcode.com/i/f14b7b8a78aa4778aa559e9b0913c0d3)完整演示了填表全过程其模式与背包问题的二维网格填充高度相似。 ## 源码级实现从暴力搜索到动态规划 仓库中该问题共提供四个递进版本的实现均可在各语言的 chapter_dynamic_programming/edit_distance.* 中找到如 [edit_distance.py](https://link.gitcode.com/i/8974584e5fab113ba6657cd6dfadc154)、[edit_distance.java](https://link.gitcode.com/i/d3c16c028e6027fc1b7215c67acf831c)、[edit_distance.cpp](https://link.gitcode.com/i/1db9fbf63d451538bf7eed4803bd166f)、[edit_distance.go](https://link.gitcode.com/i/9b14c7f5ee1f6a182738a4fa249a3a62)、[edit_distance.js](https://link.gitcode.com/i/b718a4c123ad7703f573b09d9f7dc1a2)。 ### 版本一暴力搜索递归穷举 python def edit_distance_dfs(s: str, t: str, i: int, j: int) - int: 编辑距离暴力搜索 # 若 s 和 t 都为空则返回 0 if i 0 and j 0: return 0 # 若 s 为空则返回 t 长度 if i 0: return j # 若 t 为空则返回 s 长度 if j 0: return i # 若两字符相等则直接跳过此两字符 if s[i - 1] t[j - 1]: return edit_distance_dfs(s, t, i - 1, j - 1) # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 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暴力搜索直接对应决策树模型代码忠实还原了三种操作的递归分支。其递归树中存在大量重叠子问题时间复杂度为指数级仅适合作为推导基准。版本二记忆化搜索def edit_distance_dfs_mem(s: str, t: str, mem: list[list[int]], i: int, j: int) - int: 编辑距离记忆化搜索 # 若 s 和 t 都为空则返回 0 if i 0 and j 0: return 0 # 若 s 为空则返回 t 长度 if i 0: return j # 若 t 为空则返回 s 长度 if j 0: return i # 若已有记录则直接返回之 if mem[i][j] ! -1: return mem[i][j] # 若两字符相等则直接跳过此两字符 if s[i - 1] t[j - 1]: return edit_distance_dfs_mem(s, t, mem, i - 1, j - 1) # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 insert edit_distance_dfs_mem(s, t, mem, i, j - 1) delete edit_distance_dfs_mem(s, t, mem, i - 1, j) replace edit_distance_dfs_mem(s, t, mem, i - 1, j - 1) # 记录并返回最少编辑步数 mem[i][j] min(insert, delete, replace) 1 return mem[i][j]与暴力搜索的唯一差别在于引入mem[i][j] ! -1的查表短路保证每个重叠子问题只计算一次。该版本本质是自顶向下的递归写法时间复杂度降为O(nm)。版本三二维 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]该实现严格遵循前三步推导先初始化首行首列边界条件再以正序双层循环填充内部单元格转移方程最终返回dp[n][m]。时间复杂度和空间复杂度均为O(nm)。仓库中 Java、C、Go、JS 等语言版本结构与之一致例如 edit_distance.java 中editDistanceDP函数用Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) 1实现同一转移逻辑。空间优化用 leftup 变量突破遍历顺序限制二维 dp 表能否压缩为一维关键在于转移依赖关系dp[i, j]依赖上方dp[i-1, j]、左方dp[i, j-1]、左上dp[i-1, j-1]若沿用正序遍历dp[i-1][j-1]已被本轮覆盖丢失左上方旧值若改为逆序遍历又无法预先得到左方新值dp[i, j-1]。因此两种朴素的一维遍历策略在此均不适用这与 0-1 背包、完全背包的优化情形不同。解法引入临时变量leftup在覆盖前保存左上角值dp[i-1, j-1]。此后只需考虑上方与左方两个值局面就等价于完全背包问题可以放心使用正序遍历。仓库实现如下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]关键执行顺序需要仔细理解每行开始前leftup dp[0]暂存上一行首列值随后dp[0] 1表示本行首列dp[i][0] i内层循环中先temp dp[j]记录当前即上一行j列值计算完dp[j]后将leftup更新为temp从而在下一列j1时leftup恰好等于dp[i-1][j]即下一个单元格的左上方旧值字符相等时直接dp[j] leftup不等时min(dp[j-1], dp[j], leftup) 1对应左、上、左上三个来源。优化后空间复杂度从O(nm)降至O(m)时间复杂度保持O(nm)不变。C 版本 edit_distance.cpp 中editDistanceDPComp、Go 版本 edit_distance.go 中editDistanceDPComp均采用完全相同的leftUp暂存策略可对照阅读不同语言的同构实现。运行验证与结果仓库各语言文件末尾均附带 Driver Code统一以s bag、t pack作为测试用例依次调用暴力搜索、记忆化搜索、二维 dp 与空间优化版本并打印结果例如 edit_distance.py 中的驱动代码if __name__ __main__: s bag t pack n, m len(s), len(t) # 暴力搜索 res edit_distance_dfs(s, t, n, m) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 记忆化搜索 mem [[-1] * (m 1) for _ in range(n 1)] res edit_distance_dfs_mem(s, t, mem, n, m) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 动态规划 res edit_distance_dp(s, t) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步) # 空间优化后的动态规划 res edit_distance_dp_comp(s, t) print(f将 {s} 更改为 {t} 最少需要编辑 {res} 步)四个版本对bag → pack均输出最少 4 步编辑互相印证了算法正确性。读者可在任意语言目录下直接运行对应文件验证例如python codes/python/chapter_dynamic_programming/edit_distance.py也可参考 edit_distance_test.go 中的测试写法。总结要点编辑距离莱文斯坦距离衡量两字符串相似度允许插入、删除、替换三种操作答案为最少编辑步数状态定义为dp[i][j]将s前i个字符转换为t前j个字符的最少步数dp 表尺寸(n1) × (m1)转移方程字符相等时dp[i][j] dp[i-1][j-1]不等时dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) 1边界dp[0][0] 0、首行dp[0][j] j、首列dp[i][0] i空间优化时因依赖左、上、左上三值正序与逆序单独使用均不可行须借助leftup变量暂存左上值后再正序遍历空间复杂度由O(nm)降至O(m)完整的多语言实现与逐步图解均在仓库中文档位于 ru/docs/chapter_dynamic_programming/edit_distance_problem.md代码位于各语言codes/*/chapter_dynamic_programming/edit_distance.*可对照学习。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考