1. 先把这个题目看透最短编辑距离到底在解决什么问题1.1 从拼写纠错到基因比对一个操作数的故事如果你用过手机输入法、搜索引擎的“你是不是想找”或者代码编辑器里的拼写检查其实背后都在跑同一个算法——最短编辑距离。这句话不是夸张。编辑距离Edit Distance的定义很朴素给定两个字符串 A 和 B允许对 A 做三种操作插入一个字符、删除一个字符、替换一个字符每一种操作都记一次代价问最少需要多少次操作能把 A 变成 B。这个最小操作次数就是两个字符串的编辑距离。比如kitten变成sitting最少需要 3 步把 k 替换为 s把 e 替换为 i在末尾加一个 g。这个问题最早是引用数量极高的经典论文里提出的最初就是用来研究DNA序列比对的——两条基因序列之间有多少差异能不能通过插入、删除、替换来解释彼此的演化关系。后来被拼写纠错、文本查重、语音识别、机器翻译等场景全面吸收成了字符串相似度计算的基础度量之一。对做题人来说编辑距离还有一个特殊地位它是动态规划入门必刷的经典题几乎每一个算法面试者都要跟它打一次照面。因为它足够简单——状态定义、递推关系、边界条件都很清晰又足够典型——把“最优子结构”和“重叠子问题”这两个动态规划核心特性体现得淋漓尽致。可以说吃透编辑距离等于在动态规划这条路上站稳了脚跟。1.2 暴力递归为什么走不通指数级爆炸的直觉我们先直观感受一下这个问题为什么不能用暴力枚举解决。假设 A 串长度为 mB 串长度为 n。最笨的办法是把 A 能通过所有可能的操作序列变成的所有字符串全部枚举出来看哪些等于 B再统计最短的操作数。每一步都有插入、删除、替换三种选择操作序列长度为 L 时候选总数就是 3^L 的量级。这个量级涨得有多快L10 时是五万九千多L20 时是三十四亿多。字符串长度稍微到几十个字符这个数字就已经比宇宙中的原子数量还要夸张根本不可行。暴力不行那就试试分治。把问题拆成子问题来递归假设我已经知道 A 的前 i 个字符变成 B 的前 j 个字符需要多少步我能不能从这个结果推导出更大的子问题这就是动态规划的思考起点。关键要问两个问题大问题的最优解里最后一步操作是什么除去最后一步剩余部分是不是一个规模更小但同样最优的子问题拿“最小编辑距离”来说从 A 变成 B 的任意一个最优操作序列最后一步逃不出三种情况操作完成后A 的最后一个字符恰好等于 B 的最后一个字符那么最后一步其实什么都没干问题退化为“A 的前 m-1 个字符变成 B 的前 n-1 个字符”最后一步删除了 A 的一个字符那么删除前A 的前 m-1 个字符已经变成了完整的 B最后一步插入了 B 的最后一个字符那么插入前A 已经变成了 B 的前 n-1 个字符最后一步替换了 A 的最后一个字符那么替换前A 的前 m-1 个字符已经变成了 B 的前 n-1 个字符。这四个情况每一种都把原问题缩小成了更短的字符串之间的编辑距离。而且因为最终是最优解每一步操作之前的状态也必然是对应子问题的最优解——否则我可以用更优的子问题解替换这一步得到更小的总代价。这就是“最优子结构”。递归版本的代码很简单但你很快就会发现它慢得离谱——原因是一样的子问题会被反复计算无数次。比如计算 dp(5, 5) 的时候可能已经算过几十次 dp(3, 3)每算一次都白算一次。递归树以指数速度展开跟暴力枚举本质上没有区别。要解决这个痛点就得把子问题的答案记下来只用一次。这就是动态规划的全部秘密——记忆化递归算是一种自上而下的写法而经典的二维表格递推则是自下而上的写法。两者殊途同归但二维表格递推更容易看出空间优化的路径。2. 动态规划建模从最后一步倒着走完整条路2.1 状态设计dp[i][j] 到底在记录什么动态规划最考人的一步永远是状态定义。编辑距离的状态定义其实非常自然用 dp[i][j] 表示“字符串 A 的前 i 个字符变成字符串 B 的前 j 个字符所需的最小编辑距离”。这里我强烈建议你把 A 和 B 想象成两条从左边开始伸出来的队列i 和 j 分别表示从队头数过来的长度。前 i 个字符意思是从第 1 个字符到第 i 个字符组成的子串。比如 A kitten那么前 3 个字符是kit前 6 个字符就是整个kitten。为什么状态要定义为“前缀子串与前缀子串”的距离而不是“任意子串与任意子串”的距离因为编辑过程是有顺序的从前往后处理时每一个中间状态都对应着 A 的某个前缀已经变成了 B 的某个前缀。子问题的边界因此非常清晰要么 A 这边已经耗尽i 0要么 B 这边已经耗尽j 0。如果定义成任意子串边界条件就变得非常复杂递推也很难展开。题目里最常见的解法基本都是前缀定义不是没有原因的。数组维度方面如果 A 和 B 的长度分别是 m 和 n那 dp 表就是一个 (m1) × (n1) 的表格。为什么多出一行一列因为 i 0 或 j 0 表示空字符串空字符串是合法的输入状态必须单独占位置。很多新手写代码时数组长度少写一个 1导致越界排查半天多半就是在这一步栽的。2.2 初始化边界空串与空串的距离就是对方长度初始化是编辑距离最容易翻车的环节但逻辑本身非常直白。dp[0][j]A 是空字符串要变成 B 的前 j 个字符唯一办法是逐个插入这 j 个字符所以 dp[0][j] jdp[i][0]B 是空字符串要把 A 的前 i 个字符删光所以 dp[i][0] i当然 dp[0][0] 0因为空串变空串不需要任何操作。这里有个值得多想一层的点为什么插入和删除是对称的因为编辑距离本身是对称的——从 A 变到 B 的最小步数等于从 B 变到 A 的最小步数。把 A 变成 B 的每一步操作反过来都能变成 B 变成 A 的逆操作删除变插入插入变删除替换还是一样的替换。这也就保证了 dp 表格关于主对角线是对称的初始化逻辑天然成立。边界条件写好后递推主体就有底气了。否则一上来就写转移方程边界没铺好很容易出现 dp[0][j] 参与计算的时候还是垃圾值的情况。2.3 状态转移方程为什么 min 里装的是三个子问题核心递推分两种情况讨论。第一种A[i-1] B[j-1]。这里的下标要格外小心。dp[i][j] 对应的是 A 的前 i 个字符和 B 的前 j 个字符所以 A 的第 i 个字符其实是 A[i-1]编程语言下标从 0 开始B 的第 j 个字符是 B[j-1]。这是新手经常弄混的地方也是评测机报错的重灾区。如果 A[i-1] B[j-1]那么最后一个字符已经天然对齐了不需要额外操作。此时 dp[i][j] dp[i-1][j-1]。注意这里不是 dp[i][j] dp[i-1][j-1] 0没有任何代价。这一个字符就像两块拼图刚好咬合不消耗步数。第二种A[i-1] ! B[j-1]。最后一步必须做点什么才能让两个前缀对齐有三种选择删除 A 的最后一个字符。删除后A 的前 i-1 个字符必须已经变成 B 的前 j 个字符于是 dp[i][j] dp[i-1][j] 1在 A 的末尾插入一个字符让这个新字符正好等于 B[j-1]。插入后A 的前 i 个字符必须先变成 B 的前 j-1 个字符于是 dp[i][j] dp[i][j-1] 1把 A 的最后一个字符替换成 B[j-1]。替换后A 的前 i-1 个字符需要先变成 B 的前 j-1 个字符于是 dp[i][j] dp[i-1][j-1] 1。三种操作对应三个不同的子问题取最小就得到递推公式dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])这行公式是整个算法的灵魂。很多教材直接甩给你不说为什么。我自己的理解方式是不必把这三种情况看作严格互斥的动作序列而可以想象成“我们已经站在了 dp[i][j] 这个格子上往回看一条最短路径”。每个格子都从上方、左方、左上方三个邻居迁移而来上方代表经过删除、左方代表经过插入、左上方代表经过替换或末尾字符相同时的直接继承。这就是表格递推和最短路径之间最直观的映射。2.4 手推一遍完整案例kitten 到 sitting空谈方程没用我们拿经典例子A kitten, B sitting手推一遍你就能感受到表格是怎么一层层填起来的。先写下完整个字符串A k i t t e n长度 6B s i t t i n g长度 7目标就是求 dp[6][7]。我先把表的首行首列初始化完毕然后一行一行从左往右填。为了节省篇幅我只挑关键节点解释完整表格放在后面一并呈上。当 i1A 的子串是kj1B 的子串是sk ! s取 min(dp[0][1]1, dp[1][0]1, dp[0][0]0) 1 1。这表示k变成s最小代价是替换一次。当 i2kij2si末尾字符 i 和 i 相等直接继承 dp[1][1] 1。所以ki变si还是 1 步只需把 k 换成 s。到后面 j1字母 si 从 1 增加到 6 的整列里dp[6][1] 的意思是把kitten变成s的最小步数。手工想一下先删除 kit 三个字符再替换 e 为 s不对更优的方案是把 k 替换成 s然后删除 i、t、t、e、n 五个字符共 6 步。你可以在表格里验证dp[6][1] 6。填完整张表后右下角 dp[6][7] 3这就是最终答案。前面提到的操作序列是k→s替换e→i替换末尾加 g插入三步完成。我把完整表格列出来你照着箭头逐行推一遍印象会深很多dpsitting01234567k11234567i22123456t33212345t44321234e55432234n66543323检查几个关键格dp[2][3] 表示ki变sit最短路是先把 k 替换成 s再把 i 变 i不动最后插入 t共 2 步。表格里填的确实是 2。填表的方向是严格从左到右、从上到下的因为每个 dp[i][j] 依赖的都是它的左上、上方、左方三个邻居只要这些邻居比它先算出来递推就是安全的。这也是为什么二维递推的时间复杂度稳定在 O(m×n)——每个格子只算一次每次做常数次比较。3. 代码落地与空间优化从二维表到一维数组的实战演进3.1 第一种写法递归 备忘录自顶向下动态规划有两种实现路径一种是递归加记忆化也叫自顶向下一种是填表迭代也叫自底向上。你先想清楚走哪条路再动手写代码能少踩很多坑。自顶向下思路更接近人类思考方式直接定义一个递归函数 solve(i, j)返回值是 dp[i][j] 的答案。递归出口是 i0 或 j0 时的边界值递归体里先查一下这个状态有没有算过算过就直接返回没算过就按转移方程递归计算算完存进 memo 数组。这种写法的优点是不需要显式处理填表顺序只要递归出口和转移方程写对了就能跑缺点是递归有函数调用开销深度到几千层时可能爆栈。用 Python 写大概是这样的from functools import lru_cache def min_distance_top_down(a: str, b: str) - int: m, n len(a), len(b) lru_cache(maxsizeNone) def solve(i: int, j: int) - int: if i 0: return j if j 0: return i if a[i-1] b[j-1]: return solve(i-1, j-1) return 1 min( solve(i-1, j), # 删除 a[i-1] solve(i, j-1), # 插入 b[j-1] solve(i-1, j-1) # 替换 ) return solve(m, n)lru_cache帮我们做了备忘录同样的 (i, j) 状态只会真正计算一次。不过要注意Python 递归深度默认限制在 1000 层左右如果两个字符串长度之和接近甚至超过这个值就会直接报 RecursionError。实际刷题时递归深度风险始终悬在头顶所以更常用的是下面的表格迭代法。3.2 第二种写法二维数组填表自底向上自底向上的迭代版本核心就是一个双重循环先处理边界行和边界列再逐格填充。def min_distance_dp(a: str, b: str) - int: m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min( dp[i-1][j], # 删 dp[i][j-1], # 插 dp[i-1][j-1] # 替 ) return dp[m][n]这段代码有几点很实用dp [[0] * (n 1) for _ in range(m 1)]这一行用列表推导式重新生成每一行避免了[[0] * (n 1)] * (m 1)这个经典陷阱。后者会让每一行指向同一个列表对象改一行其他行全变。这个坑我踩过排查了很久才发现是初始化的问题。外层循环按行内层循环按列顺序不能反。因为当前格 dp[i][j] 依赖的是上一行的数据按行推进才能保证上一行已经算完。函数参数建议用短变量名代码显得紧凑如果团队里有人要维护就加一行注释写上删除、插入、替换对应的子问题来源。3.3 空间优化为什么能省掉一整行又为什么必须从后往前更新二维表简单直观但仔细看就会发现算完第 i 行之后第 i-2 行及以上的数据就再也没有用了。dp[i][j] 只依赖 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]最多追溯到上一行。也就是说整个求解过程只需要保留“当前行”和“上一行”两行数据甚至更进一步可以只保留一行。用一维数组怎么做到思路是这样的滚动数组版本需要长度为 n1 的一维数组 dp 来代表当前行的结果。外层循环每推进一个 i就相当于把整个数组更新为新的一行。关键问题在于计算 dp[j] 时原来的 dp[j-1] 已经被本轮覆盖成新值了不再是上一行的 dp[i-1][j-1]那这个左上角值怎么拿答案是在内层循环开始前用一个变量 prev 记录上一轮的 dp[j-1] 的旧值。每算完一个新的 dp[j]再把 prev 更新成没有被覆盖前的旧 dp[j]用于下一轮的左上角计算。还有一个副产物是上一轮 dp[j] 的旧值也就是上一行的 dp[i-1][j]它在被覆盖之前我们还有机会读到——实际上如果我们在更新 dp[j] 之前额外用一个变量保存当前 dp[j] 的旧值那这个旧值正是 dp[i-1][j]正是删除操作对应的那个子问题。代码是这样def min_distance_optimized(a: str, b: str) - int: m, n len(a), len(b) dp list(range(n 1)) # dp[j] dp[0][j] for i in range(1, m 1): prev dp[0] # 保存左上角相当于 dp[i-1][0] dp[0] i # dp[i][0] i for j in range(1, n 1): old dp[j] # 保存旧值相当于 dp[i-1][j] if a[i-1] b[j-1]: dp[j] prev else: dp[j] 1 min(prev, dp[j], dp[j-1]) prev old # 下一次的左上角就是这次被覆盖前的 dp[j] return dp[n]这段代码我第一次写的时候绕了很久尤其是 prev 的更新时机。后来总结成一个口诀内层循环每一步开始时prev 保存的是“上一行、左一列”的值dp[j] 保存的是“上一行、本列”的值dp[j-1] 已经是“当前行、左一列”的值。三者刚好齐活。时间复杂度和二维版本完全一样O(m×n)空间从 O(m×n) 降到了 O(n)。如果题目严格要求最小化空间还可以先比较 m 和 n 的大小让外层循环遍历较短的那个字符串这样滚动数组长度永远是 min(m,n)1局部性能会更好一点。3.4 复杂度边界数据规模怎么选方案面试或笔试里编辑距离的输入规模通常是几百到几千。O(m×n) 的时间复杂度在 mn1000 时是 10^6 量级完全能扛mn5000 时是 2.5×10^7勉强也能过但如果到 10^4 量级纯 O(mn) 就吃力了需要考虑更复杂的优化思路比如带带限制的编辑距离、分治加剪枝等高级手法。空间方面如果题目只要求输出最小操作数一维滚动数组是稳赚不亏的空间从 O(mn) 降到 O(min(m,n))但如果你要回溯具体操作序列就必然需要完整的二维表这时空间 O(mn) 是必须付出的代价。这里有个实用建议先问自己到底需不需要还原路径再决定用哪种空间方案而不是一上来就无脑写滚动数组。4. 高频坑点与排查技巧这些坑我替你踩过了4.1 下标偏移经典错误dp 表长度是 n1 不是 ndp[i][j] 表示前缀长度前缀长度可以取到 0所以数组长度必须是原字符串长度加 1。很多人初始化数组时下意识写(m, n)结果外层循环到 im 时越界或者漏算空串到空串的情况。排查思路很简单手动跑一遍长度为 1 的字符串对比如 aabb看 dp 表是不是 2×2边界值是不是 dp[0][0]0、dp[0][1]1、dp[1][0]1。如果初始化成 1×1第一个格子就存不下这么多信息。4.2 滚动数组的左上角值丢失全表结果错乱一维滚动数组最大的隐患是 prev 更新时机不对。常见错误是写成prev dp[j] dp[j] min(...)结果 prev 变成了新值左上角信息全部错乱最后答案完全不对。调试这类问题最好的办法是用小例子打印每次循环后的 dp 数组盯着 prev 和 dp[j-1] 看比对二维表的对应行。我习惯写一个 debug 函数把二维表和一维数组同步打印出来一眼就能看出哪一轮开始漂了。4.3 不只是计算距离如何回溯输出完整操作序列很多题目会要求你输出具体的操作步骤第几步把哪个字符替换/插入/删除了。这就需要一个 trace 数组或直接在二维表上做回溯。回溯的核心逻辑从右下角 dp[m][n] 开始向左上角走如果 a[i-1] b[j-1]说明这个字符是直接继承的不需要操作i--、j--如果 dp[i][j] dp[i-1][j] 1说明这一步是删除记录“删除 a 的第 i 个字符”i--如果 dp[i][j] dp[i][j-1] 1说明这一步是插入记录“在 a 的第 i 个位置后插入 b[j-1]”j--否则就是替换记录“把 a 的第 i 个字符替换为 b[j-1]”i--、j--。注意当多个方向同时满足条件时随便选一条走出来都是最短路径之一不必担心唯一性。以下代码演示如何输出操作序列def edit_distance_with_steps(a: str, b: str): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) ops [] i, j m, n while i 0 or j 0: if i 0 and j 0 and a[i-1] b[j-1]: i - 1 j - 1 elif i 0 and dp[i][j] dp[i-1][j] 1: ops.append(f删除第 {i} 个字符 {a[i-1]}) i - 1 elif j 0 and dp[i][j] dp[i][j-1] 1: ops.append(f插入字符 {b[j-1]}) j - 1 else: ops.append(f替换第 {i} 个字符 {a[i-1]} 为 {b[j-1]}) i - 1 j - 1 ops.reverse() return dp[m][n], ops这段代码有几个容易写错的地方while 循环的条件必须是i 0 or j 0因为在删除或插入操作中可能一个下标已经归零而另一个还没归零判断相等的分支放在最前面否则会误判成替换append 之后要反转列表因为我们是从后往前回溯的。4.4 边界条件速查表常见输入组合输入组合预期结果原因A , B 0空串变空串A , B abc3插入三个字符A abc, B 3删除三个字符A abc, B abc0完全相同不动A abc, B abd1替换 c 为 dA a, B b1替换A ab, B ba2替换两处或先删后插这些边界值值得你在写完代码后立刻自测一遍。只要有一条不满足基本可以断定代码逻辑存在问题不用专门等评测机上的大量数据拖慢定位速度。4.5 编辑距离的经典变种从 LCS 到加权编辑距离学编辑距离不只是为了一道题它还牵扯出一整个字符串问题家族。最经典的是最长公共子序列Longest Common SubsequenceLCS。LCS 和编辑距离的转移方程几乎一模一样区别是 LCS 的状态定义是“长度”而不是“代价”dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列长度字符相等时 dp[i][j] dp[i-1][j-1] 1不相等时取 max(dp[i-1][j], dp[i][j-1])。这两者还有一个有趣的数学关系如果只允许插入和删除不允许替换那么编辑距离 m n - 2 × LCS(A, B)。直观理解是先用删除把 A 中不属于公共子序列的部分删掉再用插入把 B 多出来的部分补上。替换操作本质上就是“先删除再插入”的二合一所以允许替换时距离可能更小。面试官经常在写完编辑距离后追问一句“如果去掉替换操作怎么写”本质上就是在考这个关系。另一个常见变种是加权编辑距离插入、删除、替换的代价不再都是 1比如替换更贵、插入更便宜。这时转移方程只需要把1分别换成对应的代价即可整体表格结构不变。很多工业级拼写纠正系统里权重是根据键盘距离设置的——相邻键位的误敲替换代价更低距离远的键位替换代价更高这比统一权重更能反映真实输入错误模式。5. 写在最后的一点个人体会我自己第一次学编辑距离时卡在的不是递推方程本身而是“为什么这样拆最后一步就一定对”。后来用二维表格自己一行一行填了两个小例子突然就通了——每个 dp[i][j] 都是站在前人肩膀上算出来的路径越短前面的每一步也必须短。这个“全局最优必由局部最优构成”的直觉比记忆公式重要得多。如果你也是刚开始学动态规划我建议别急着背代码。先拿 kitten 和 sitting 这种小例子手算一遍表感受到每个格子的数字从哪来再打开编辑器自己默写一遍三行转移方程最后再碰滚动数组优化。这些流程走完基础就算真正打牢了。编辑距离之后最长上升子序列、最长公共子序列、背包问题都只是同样的套路换了一身皮你的思维一旦过了这个坎后面会顺很多。