算法学习台/算法实验台/56 天打卡/141 题/LC72
题型地图56天全屏141题

当前：LC72 · 编辑距离:把一个单词修成另一个 · 首次出现于 Day 39 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC70LC73 →
28 / 141回到 Day 39 卡片141 题索引
LC72动态规划文字修复工坊 · 二维 DP状态表账本

编辑距离:把一个单词修成另一个

word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。

题目是什么

word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。

解决什么问题

当前格依赖哪些已知状态，为什么这些状态已经计算完成？

核心结论

dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。

01交互算法精讲

先说结论：这道题到底解决什么

怎样从“word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。”推导出 文字修复工坊 · 二维 DP，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。

读完必须能回答
  1. 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
  2. 2.当前格依赖哪些已知状态，为什么这些状态已经计算完成？
  3. 3.不变量“dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。”为什么能保证算法安全前进？
02交互算法精讲

完整题目与题意拆解

word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。

在本站主例中，word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。

算法最终需要得到或观察：右下角 dp[m][n] = 3,即把 horse 修成 ros 最少需要 3 刀。

把题目翻译成状态
  • • 输入：word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。
  • • 机器需要维护：完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。
  • • 最终可观察结果：右下角 dp[m][n] = 3,即把 horse 修成 ros 最少需要 3 刀。
动画 1 · 题意扫描

先看清算法到底要维护什么

先建立输入、目标、输出和第一批状态，不急着进入模板。

Step 1/20%
任务出现把 “horse” 修成 “ros”

把 “horse” 修成 “ros”

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
03交互算法精讲

第一层方案：暴力做法

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

动画 2 · 暴力重复

重复工作究竟发生在哪里

把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。

Step 1/20%
先做对：建立暴力基线枚举所有候选并完整验证

把 “horse” 修成 “ros”

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
优化方向：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。
04交互算法精讲

整体地图：先做什么，再做什么

  1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
  2. 2状态只维护 完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。
  3. 3转移每一步按照 dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。
  4. 4收尾读取 右下角 dp[m][n] = 3,即把 horse 修成 ros 最少需要 3 刀。，并复核边界与复杂度。
05交互算法精讲

状态表账本：核心概念

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。

核心不变量
  • • dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。
  • • 填到 (i,j) 时,左方、上方、左上方三格一定已经被填好。
动画 3 · 核心概念

建立“状态表账本”心智模型

用主例建立核心状态，先预测下一步，再公开正确分支和理由。

Step 1/40%
任务出现把 “horse” 修成 “ros”

把 “horse” 修成 “ros”

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
06交互算法精讲

核心机制：状态如何一步步变化

dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。

执行过程中持续维护：完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。

正确性依赖以下不变量：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。；填到 (i,j) 时,左方、上方、左上方三格一定已经被填好。

面试时可以压缩为：二维 DP,dp[i][j]=word1 前 i 位到 word2 前 j 位的最少操作。末字符相等则继承 dp[i-1][j-1],否则三种操作取 min 再 +1。时间 O(mn),空间 O(mn),可用滚动数组压到 O(min(m,n))。

落到当前题，执行机制可以压缩为：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

动画 4 · 机制构建

一次状态转移为什么成立

集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。

Step 1/50%
原点 dp[0][0] = 0空串变空串,代价 0

空串变空串,代价 0

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
07交互算法精讲

正确性证明：为什么不会漏答案

初始化

初始化：算法开始时，全部合法候选仍在状态表示范围内；dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。

保持

保持：执行“dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。”时，只删除已经能证明不可能的候选，并把新信息写回 完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。

终止

终止：没有待处理状态或达到命中条件时，当前可观察结果就是“右下角 dp[m][n] = 3,即把 horse 修成 ros 最少需要 3 刀。”。

正确性抓手不是“样例跑通”，而是每一帧结束后仍能复述：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。；填到 (i,j) 时,左方、上方、左上方三格一定已经被填好。
08交互算法精讲

完整执行过程

  1. 1任务出现给你一个原字 “horse”,一个目标 “ros”。你可以插入、删除、替换字符,问最少几刀。 因为：LC72 编辑距离:求 word1 到 word2 的最小操作次数,操作集为 insert / delete / replace。
  2. 2dp[0][1] = 1第一行:左边是空字符串,要拼出右边的 “r”,唯一办法是插入 1 个字符。 因为：dp[0][j] = j。空串需要 j 次插入才能变成 word2 前 j 位。
  3. 3dp[2][0] = 2第一列:右边是空字符串,要把 “ho” 全删光,需要 2 次删除。 因为：dp[i][0] = i。word1 前 i 位必须全部删除才能变成空串。
  4. 4dp[1][2] = 2比较 “h” 和 “o”,三种动作中 把 “h” 换成 “o” 最便宜,本格记 2。 因为：dp[1][2] = 1 + min(dp[0][2], dp[1][1], dp[0][1]) = 2 (取 替换)。
  5. 5dp[3][1] = 2当前比较 “r” 和 “r”——一样,直接抄左上角,什么都不动。 因为：word1[2]==word2[0],dp[3][1] = dp[2][0]。
  6. 6dp[4][3] = 2当前比较 “s” 和 “s”——一样,直接抄左上角,什么都不动。 因为：word1[3]==word2[2],dp[4][3] = dp[3][2]。
  7. 7第 1 刀 · 替换把第 1 位的 “h” 替换成 “r”。 因为：执行 替换,得到 “rorse”。
  8. 8面试总结面试官想听的:状态定义、初始化、转移方程、复杂度。下面这块就是标准答案。 因为：dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。dp[i][0]=i,dp[0][j]=j。若末字符相等,dp[i][j]=dp[i-1][j-1];否则 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。时间 O(mn),空间 O(mn)(滚动数组可降为 O(n))。
动画 5 · 完整执行

从输入完整走到可观察结果

从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。

Step 1/80%
任务出现把 “horse” 修成 “ros”

把 “horse” 修成 “ros”

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
09交互算法精讲

把动画和 Go 代码逐行对应

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

动画 6 · 代码映射

让每个动作都落到 Go 分支

重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。

Step 1/60%
任务出现把 “horse” 修成 “ros”

把 “horse” 修成 “ros”

h·
o·
r·
s·
e·
→·
r·
o·
s·
WORD1horse
WORD2ros
ANS3
10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
            }
        }
    }
    return dp[m][n]
}

func min3(a, b, c int) int {
    if a < b && a < c { return a }
    if b < c { return b }
    return c
}
最小测试集合
func main() {
    // 1. 主例
    //    输入：mode="edit-distance", a="horse", b="ros"
    //    期望：右下角 dp[m][n] = 3,即把 horse 修成 ros 最少需要 3 刀。
    //
    // 2. 失败 / 未命中
    //    检查：复杂度不是 O(n)/O(1):二维 DP 时间 O(mn) 空间 O(mn),滚动数组才能压到 O(min(m,n))。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC583 两字符串删除操作；LC1143 最长公共子序列；LC97 交错字符串
}
11交互算法精讲

正确性与复杂度

时间复杂度 O(mn)

执行过程中只保留仍可能影响答案的状态。dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。

空间复杂度 O(mn)

额外状态主要用于维护：完整二维表 dp,大小 (m+1)×(n+1),逐行从左到右填。

终局不变量
  • • dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。
  • • 填到 (i,j) 时,左方、上方、左上方三格一定已经被填好。
12交互算法精讲

最容易写错的地方

错误 1

复杂度不是 O(n)/O(1):二维 DP 时间 O(mn) 空间 O(mn),滚动数组才能压到 O(min(m,n))。

错误 2

初始化要写满第一行 dp[0][j]=j 与第一列 dp[i][0]=i,代表空串到前缀的距离。

错误 3

字符索引下标差 1:比较的是 word1[i-1] 与 word2[j-1],不是 word1[i]。

边界复查

必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1题意word1="horse",word2="ros",问最少几刀(插入/删除/替换)能修成目标。
  2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
  3. 3优化dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作。末字符相同则继承左上角;否则取 min(上方+1, 左方+1, 左上+1)。
  4. 4证明dp[i][j] = word1 前 i 位变 word2 前 j 位的最少操作数。；填到 (i,j) 时,左方、上方、左上方三格一定已经被填好。
  5. 5复杂度时间 O(mn)，空间 O(mn)
面试表达：二维 DP,dp[i][j]=word1 前 i 位到 word2 前 j 位的最少操作。末字符相等则继承 dp[i-1][j-1],否则三种操作取 min 再 +1。时间 O(mn),空间 O(mn),可用滚动数组压到 O(min(m,n))。
迁移练习
  • • LC583 两字符串删除操作
  • • LC1143 最长公共子序列
  • • LC97 交错字符串