编辑距离：结尾一对字符，只在增删改里挑
dp[i][j] 只回答「A 的前 i 个字变成 B 的前 j 个字要几步」。末尾相同就白嫖左上；不同就在删、增、改三个邻居里取最小再加一。
dp[0][j]=j、dp[i][0]=i（空串基线）。若 A[i−1]==B[j−1]，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(m·n)，空间可压 O(min)。
给你两个单词 word1 和 word2，每次可以对 word1 做插入一个字符、删除一个字符、或替换一个字符，求把它变成 word2 的最少操作次数。三种操作代价都是 1，没有「免费改写一整段」。
主例 word1 = horse，word2 = ros。一条最短改法是 horse → rorse（h 换成 r）→ rose（删掉多余的 r）→ ros（删掉 e），一共 3 次。演示表的右下角 dp[5][3]=3，记的就是这个数。
枚举所有操作序列能做对，但每一步都有三种选择，长度一长就是指数级。本文要回答：为什么只要看两个前缀的结尾字符，以及主例里「相等继承」和「三选一加一」分别落在哪一格。
缺口是前缀距离，不是整串操作清单
第一直觉是从 horse 出发，试插入、删除、替换，直到撞上 ros。最短路能搜到 3，但同一对前缀会被反复算：先删后改、先改后删，走到「ho 对 ro」这种中间态会重复出现。缺的不是「最后改成了什么」，而是一个可以复用的小问题：A 的前 i 个字符变成 B 的前 j 个字符，最少几步。
一旦问题收成前缀，当前这一对结尾字符就只有两种关系。相等：最后一个字不用动，整段距离等于去掉这两个字之后的距离。不等：最后一个字必须用一次操作收拾——删掉 A 的尾、插入 B 的尾、或把 A 的尾改成 B 的尾。没有第四种与结尾有关的合法动作。
用表格记账。行对应 A 的前缀长度 0..5，列对应 B 的前缀长度 0..3。dp[i][j] 就是 A[0:i] → B[0:j] 的最少步数。空串对空串是 0。空串变成 ros 的前 j 个，只能插入 j 次，所以第一行是 0,1,2,3。horse 的前 i 个变成空串，只能删除 i 次，所以第一列是 0,1,2,3,4,5。基线不是装饰，后面每一格都踩在它们上面。
格子的几何方向和三种操作一一对应。来自上方 dp[i−1][j]：已经把 A 的前 i−1 个变成了 B 的前 j 个，再删掉 A[i−1]。来自左方 dp[i][j−1]：已经把 A 的前 i 个变成了 B 的前 j−1 个，再插入 B[j−1]。来自左上 dp[i−1][j−1]：已经对齐了更短的两个前缀，再替换当前这对结尾——若结尾本来就相等，这一步费用是 0，直接继承左上。
用手走主例几格关键格子。dp[1][1] 比的是 h 和 r，不相等：1 + min(删=1, 增=1, 改=0) = 1，也就是把 h 换成 r。「h」变「r」一步够了。dp[2][2] 比的是第二个字母，两边都是 o，相等，继承左上 dp[1][1]=1：「ho」变「ro」仍然只改了开头那个 h。dp[3][1] 比的是 r 和 r，相等，继承 dp[2][0]=2：「hor」变「r」等于删掉 h 和 o。
继续往右下走。走到「hors」对「ros」时，末尾都是 s，继承上一格「hor」对「ro」。最后一格 dp[5][3] 比的是 e 和 s，不相等：删 e、在末尾插 s、或把 e 改成 s，三者取最小再加一，得到 3。演示场景整张表填满后，右下角停在 3，对应 horse → ros。
三种操作必须同时开放。只许删，horse 和 ros 没有公共子序列可对齐到 3；只许改、不许增删，长度 5 对 3 根本对不齐。LC583 去掉替换、只留删除，就是这张表的退化：不等时不再看左上那条「改」的边。面试里把转移说成「看结尾相不相等，不等就三选一」即可，不必背操作名字的英文。
三种操作映射删=来自上方、增=来自左方、改=来自左上。相等不是第四种操作，是「改」的费用掉成 0，所以直接抄左上。主例 dp[2][2] 的两个 o 就是这样白嫖的。
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 2 | 3 |
| r | 3 | 2 | 3 | 3 |
| s | 4 | 3 | 3 | 3 |
| e | 5 | 4 | 4 | 3 |
Go：二维 DP
func minDistance(a, b string) int {m, n := len(a), len(b)dp := make([][]int, m+1)for i := 0; i <= m; i++ {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 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]}func min(a, b, c int) int {if a > b { a = b }if a > c { a = c }return a}
1行 0 和列 0 先垫空串基线：全插入、全删除。主例第一行 0,1,2,3，第一列 0..5。
2a[i-1]==b[j-1] 时抄左上。下标是 i-1、j-1，因为 dp 的 i、j 是前缀长度，比字符下标多 1。
3不等则 1+min(上, 左, 左上)，对应删、增、改。漏掉其中一条，horse→ros 就到不了 3。
4答案只在右下角 dp[m][n]。中间格是脚手架，不必回溯出具体操作也能交题。
总结
前缀对前缀：结尾相同抄左上，不同就删/增/改三选一加一。horse→ros 答案 3。
- 缺的是「两个前缀的距离」，不是整串操作清单。暴力搜操作会把同一对前缀算许多遍。
- 上、左、左上分别是删 A 尾、增 B 尾、改尾。相等是改的费用为 0。
- LC583 只允许删除，是这张表去掉「改」之后的退化。