编辑距离动态规划全解：状态定义、转移方程与滚动数组优化

这段时间集中刷力扣动态规划专题一路做下来0226这道题卡了我将近一个晚上。后来我在刷题笔记里给它专门标了个“必考题”原因很简单——它把二维动态规划里最难讲清楚的三个东西一次全暴露了状态怎么定义、边界怎么初始化、空间怎么优化。先声明一下这个 0226 是我自己在刷题笔记里排的编号跟力扣官方题号不是一回事。官方题号不重要重要的是这类题背后的方法论。为了方便叙述我把题目还原成最经典的那个场景给定两个字符串 s 和 t可以对 s 做三种操作插入一个字符、删除一个字符、替换一个字符问把 s 变成 t 最少需要多少次操作。这就是很多人面试时遇到的“编辑距离”问题。它解决的现实需求很直观文本 diff 工具里要对比两个文件差了几行、拼写检查软件要猜你打错的那个词最接近哪个正确词、甚至基因序列比对里也能看到它的影子。所以不管你是刚开始学 DP 的小白还是准备面试想系统刷一遍高频题的老手把这道题吃透都特别值。1. 题目拆解与 DP 识别为什么第一反应该想到动态规划1.1 先别急着写代码把操作含义盘明白很多人一看到“最少操作次数”这种表述脑子里就开始倒腾贪心策略是不是每次挑最优的操作就行我也试过结果发现贪心在这里根本站不住脚。给你一个很简单的反例s abt ba。如果只看当前字符s[0] 是 at[0] 是 b你可能会想把 a 替换成 b然后第二个字符再把 b 替换成 a一共 2 次替换。最优解其实只需要 2 次也不是其实是 2 次但这个例子里替换和“删掉一个再插入一个”效果一样问题在于当字符串更长时某个局部看起来最优的操作可能会让后面的字符全部错位最后反而多花好几步。这个现象背后藏着一个关键结构当前这一步怎么选会影响后面一系列步骤的状态。什么时候会出现这种事当问题可以被拆成规模更小的子问题而且子问题之间有重叠时就是典型的动态规划信号。1.2 最优子结构和重叠子问题两个信号一个都不能少编辑距离为什么具备这两个信号我们盯着 s 和 t 的最后一个字符看。如果 s 的最后一位和 t 的最后一位已经相等了那实际上我们只需要解决前面部分的转换问题最后一个字符不用动。如果不等我们有三条路替换 s 的最后一个字符让它等于 t 的最后一个字符然后解决前面部分的转换删除 s 的最后一个字符然后解决剩下来的 s 前缀和完整 t 之间的转换在 s 的末尾插入一个字符让它去匹配 t 的最后一位然后解决完整 s 和新 t 前缀之间的转换你看不管走哪条路最终都落回到“把某个前缀变成某个前缀”这个更小的问题上而且不同的选择路径会反复遇到同样的子问题。我拍脑袋算了算如果纯递归去解每次分 3 个叉深度是 mn整体复杂度直接指数爆炸。但用动态规划把这些子问题的答案存下来每个子问题只算一次复杂度瞬间就降下来了。这就是我反复跟人强调的那个判断标准——不是因为题目里带个“最少”就是 DP而是因为大问题能拆小、小问题互相重叠这才是 DP 的主场。2. 状态定义与转移方程把“直觉”翻成公式2.1 dp[i][j] 为什么这样定义动态规划最核心的一步就是给状态一个精确的含义。我见过太多人卡在这一步状态定义得含糊后面全乱。这题我建议这样定义dp[i][j] 表示字符串 s 的前 i 个字符转换成字符串 t 的前 j 个字符需要的最少操作次数。注意这里说的是“前 i 个”和“前 j 个”不是“第 i 个”和“第 j 个”。这个细节极其重要。用“前 i 个”而不是“下标到 i”可以让我们在 i 0 或 j 0 的时候直接对应“空字符串”这个状态处理边界特别自然。如果定义成“第 i 个字符到第 j 个字符”你还要单独处理空串的情况状态下标也会绕来绕去。拿一个具体例子试一下。s horset ros。dp[3][2] 表示 hor 变成 ro 的最少步数。我们最终要的答案就是 dp[5][3]。2.2 转移方程的三种来源一次讲透现在来推导核心的转移方程。假设我们已经算出了所有比 (i, j) 规模更小的子问题想要算 dp[i][j]。分两种情况情况一s[i-1] t[j-1]最后一个字符已经相等不需要额外操作。当前问题直接继承 dp[i-1][j-1]。这里很多人会犯迷糊想着“是不是还可以删掉这个相等的字符再插回来也能得到同样结果”理论上可以但步数会多 2 步最小步数一定不会选它。所以直接用继承。情况二s[i-1] ! t[j-1]这时候必须做一次操作。三个选择对应三次子问题替换把 s[i-1] 改成 t[j-1]那么前面 i-1 个字符要变成前面 j-1 个字符代价是 dp[i-1][j-1] 1删除把 s[i-1] 删掉那么剩下的前 i-1 个字符要变成完整的前 j 个字符代价是 dp[i-1][j] 1插入在 s 的末尾补一个 t[j-1]让新字符去匹配 t 的最后一个字符原 s 的前 i 个字符要变成 t 的前 j-1 个字符代价是 dp[i][j-1] 1。三者取最小值。这三个下标关系我建议不要死记每次写的时候自己画一画字符串就清楚了。我最开始学的时候反复搞混“插入对应 dp[i][j-1] 还是 dp[i-1][j]”后来找到一个记忆方法你插入的是 s 这边的字符但匹配的是 t 的最后一个字符所以 t 的规模变小了也就是 j 变成 j-1。同理删除删的是 s 的字符s 的规模变小也就是 i 变成 i-1。2.3 边界初始化空串到非空串只有一条路边界情况是整个二维表中的第一行和第一列。dp[0][j] 表示空字符串 s 变成 t 的前 j 个字符能怎么办只能一个一个插入所以 dp[0][j] j。dp[i][0] 表示 s 的前 i 个字符变成空字符串只能一个一个删除所以 dp[i][0] i。这两个边界看似简单但如果漏了后面整张表都会算错。我经常看到有人给 dp 数组开好了 (m1) x (n1) 的尺寸却忘记给第一行第一列赋值结果算出来的答案全偏。为了让你彻底看懂我手算一个完整的例子。s horset ros表格初始化之后长这样dp空ros空0123h1o2r3s4e5逐行填。第一行处理完你会发现整个转移过程就是把“当前字符是否相等”这个判断翻译成一个 min 运算。填完之后右下角的 dp[5][3] 是 3也就是说 horse 变成 ros 最少需要 3 次操作h 替换成 r、删除 e、删除 o 前面的一个具体路径是什么大家填完表可以自己倒推一下。3. 代码实现与空间优化从二维变一维到底在优化什么3.1 基础版先写二维把逻辑跑通我写题一直有个习惯先把最直白的版本写正确再谈优化。直接一上来写一维滚动数组很容易把自己绕晕。先看二维版本def min_distance(s: str, t: str) - int: m, n len(s), len(t) 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 s[i - 1] t[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j - 1], # 替换 dp[i - 1][j], # 删除 dp[i][j - 1] # 插入 ) 1 return dp[m][n]迭代顺序是外层 i、内层 j从左到右、从上到下。为什么这个顺序对因为 dp[i][j] 依赖的是左上角 dp[i-1][j-1]、正上方 dp[i-1][j]、正左方 dp[i][j-1]这三个位置在当前格子被计算之前都已经被算过了。只要保持这个双重循环依赖关系就不会被破坏。时间复杂度 O(m * n)空间复杂度也是 O(m * n)。这个版本已经能通过力扣的测试。但面试官通常会追问一句能不能把空间省下来3.2 滚动数组优化只保留上一行但左上角要单独存观察一下转移方程你算第 i 行的时候其实只需要第 i-1 行的数据更早的行用不到了。所以可以用一个长度为 n1 的一维数组反复更新。这就是经典的“滚动数组”思路。但这里面藏着一个最常见的坑dp[i-1][j-1] 即左上角的值在滚动更新过程中很容易被覆盖掉。你想我们用一维数组时dp[j] 同时承担了“上一行的第 j 列”和“当前行的第 j 列”两个角色。如果直接在一行内从左往右刷新 dp[j]那么当你算 dp[j] 时dp[j-1] 已经被刷新成当前行的值了不再代表左上方。解决办法是在更新 dp[j] 之前用一个临时变量把旧值存下来也就是上一行的 dp[j-1]。我当时的实现长这样def min_distance_scroll(s: str, t: str) - int: m, n len(s), len(t) dp [j for j in range(n 1)] for i in range(1, m 1): prev dp[0] # 上一行的 dp[i-1][0] dp[0] i # 当前行的 dp[i][0] for j in range(1, n 1): temp dp[j] # 保存未更新前的 dp[j]即 dp[i-1][j] if s[i - 1] t[j - 1]: dp[j] prev # 这里的 prev 就是 dp[i-1][j-1] else: dp[j] min(prev, dp[j], dp[j - 1]) 1 prev temp # 下一轮循环时这个 temp 会成为新的“左上角” return dp[n]这段代码我第一次写的时候没加 temp 变量结果跑出来的全是错的。给大家一个排查经验只要结果比真实答案大十有八九是把某个旧值弄丢了如果结果比真实答案小大概率是错误地复用了被新值覆盖的位置。这个观察在各类滚动数组题里都适用。空间复杂度从 O(m * n) 降到 O(n)。严格来说如果 m 和 n 相差很大还可以先交换两个字符串让 n 取较小的那个进一步省空间。3.3 工程上还有哪些变体值得了解在实际业务里我们有时不只想要“最少步数”还想知道“具体做了哪些操作”。比如文件对比工具要标出哪几行被修改了。这时候光靠一个 int 数组不够至少要加一个同尺寸的路径记录数组记录每个格子是从哪个方向转移来的。最后从右下角反推回去就能还原完整的操作序列。这个思路很多题通用比如迷宫最短路径、最小代价路径都这么干。另外如果两个字符串特别长比如上万字符的基因序列O(m * n) 的时间可能扛不住。工程上会用分块算法或者近似算法这是另一套话题了但面试阶段能把 O(m * n) 的时空版本写清楚已经很扎实。4. 踩坑实录边界条件与细节问题排查4.1 初始化与下标偏移占这类题 80% 的错我复盘了一下自己写编辑距离的报错记录基本集中在几个地方。第一个是 dp 数组维度。很多人习惯直接用 m 行 n 列的数组然后强行在循环里处理边界结果越写越乱。正确姿势就是 m1 行、n1 列用“前 i 个字符”这种语义来对应空串。第二个是初始化被跳过。有人写了首行首列的初始化但在双层循环里把 i 从 0 或 j 从 0 开始跑导致边界又被覆盖。循环必须从 1 开始0 那行那列是地基不要动。第三个是下标偏移。s[i-1] 和 t[j-1] 是当前要比较的字符s[i] 和 t[j] 是“还没处理到”的字符。这个偏移错一位整个状态就全错了。4.2 测试用例怎么设计才能“稳”经验告诉我字符串类 DP 题的测试用例一定要覆盖这几类两个空串结果应该为 0一个空串一个非空串结果应该等于非空串长度两个完全相同的字符串结果应该为 0两个完全没有公共字符的字符串比如 abc 和 def结果应该是 3一个大字符串包含小字符串中的全部字符比如 horse 和 ros。这种“边界 极端 常规”的用例组合对我来说是刷一切 DP 题的标配。我记得有一次给一个学员讲这题他写出来代码跑样例全过交上去却超时。后来发现他在每一层循环里都调用了.append()来构建新列表导致常数开销巨大。改成预分配列表之后直接快了 20 倍。刷题时如果你不确定性能瓶颈在哪先检查循环里有没有隐藏的 O(n) 操作别急着怀疑算法复杂度。5. 从编辑距离到整个 DP 题型的举一反三5.1 和最长公共子序列的关系一句话就通编辑距离模型里如果操作的代价不是 1而是插入删除代价为 1、替换代价为 2那么这个问题就跟最长公共子序列LCS直接挂钩了。核心观察是任何编辑操作都可以理解为“保留 LCS 中的字符不动其余字符要么删、要么插”。所以当替换代价很高时最优策略一定是尽可能多地保留公共部分。LCS 的状态定义是 dp[i][j] 表示 s 前 i 个字符和 t 前 j 个字符的最长公共子序列长度转移方程几乎和编辑距离同构s[i-1] t[j-1] 时dp[i][j] dp[i-1][j-1] 1不相等时dp[i][j] max(dp[i-1][j], dp[i][j-1])。把这两个题放在一起对比着刷效果比我单独刷十道题还好。因为它们共享同一副“骨架”只是每个状态位上的聚合方式不同一个是取 min一个是取 max。5.2 更多相似模型区间 DP 与线性 DP 的识别编辑距离、LCS 这类题目特征是“两个序列互相匹配”叫双序列 DP。还有一类常见的是单序列上的区间 DP比如“最长回文子序列”。它的状态是 dp[i][j] 表示 s[i...j] 区间内的答案转移时看 i 和 j 两个端点是否相等。如果不相等取去掉左端点或去掉右端点两个子问题的较大值。很多朋友分不清什么时候用线性 DP、什么时候用区间 DP。我的粗糙但好用的判断方法如果状态转移只依赖“前一个位置”或“上一层”那是线性 DP如果转移需要同时考虑“左端点”和“右端点”并且子问题是连续区间那就是区间 DP。编辑距离虽然有两个维度但它的依赖是线性的属于双序列线性 DP。两者套路不同但状态定义的思路一脉相承。5.3 OP 表格常见 DP 题型一眼识别类型常见信号词状态设计习惯典型例子线性 DP序列、爬楼梯、打家劫舍dp[i] 表示前 i 个元素的结果一维数组的递推双序列 DP两个字符串、最小编辑距离dp[i][j] 表示两序列前缀匹配结果编辑距离、LCS区间 DP回文子序列、戳气球dp[i][j] 表示区间 i 到 j 的结果最长回文子序列背包 DP容量、选或不选、最大价值dp[c] 表示容量为 c 时的最优值0-1 背包、分割等和子集树形 DP树状结构、依赖关系dp[node] 表示以该节点为根的子树结果打家劫舍 III这张表不是让你背而是提醒你拿到题目先归类再想状态最后再写状态转移。顺序反了代码写出来大概率是糊的。6. 我刷完这道题后的复盘方法最后再分享一点自己的想法。刷动态规划最忌讳的是“看完题解觉得懂了关上屏幕又写不出来”。我自己总结了一个三遍刷题法专门对付这种情况。第一遍拿到题目先自己想 15 分钟。想不出来就直接看题解但只看状态定义和转移方程不要看代码。然后合上题解自己把代码写出来。第二遍当天晚上再重新做一遍这道题要求自己不看任何参考资料独立写完全部代码和测试用例。这一遍如果卡住说明某些细节还没真正消化需要立即回去翻。第三遍一周之后再来一次这时候重点不是写代码而是尝试用口头把“为什么状态要这么定义、为什么转移方程是这三项取 min”讲清楚。能讲清楚才算真的吃透了。0226 这道题我大概刷了三遍每一遍都有新发现。第一遍学会了标准解法第二遍意识到滚动数组的临时变量容易坑人第三遍才真正理解了它和 LCS 共用同一副骨架。这大概就是刷题最实在的乐趣同一道题在不同阶段反复做你会清晰地看到自己的成长轨迹。如果你正在刷力扣的动态规划专题正好也做到类似的编辑距离题目我建议你别急着跳过多花点时间把状态转移的“为什么”彻底想明白。这一题想通了后面遇到双序列 DP 的变体你会轻松很多。