编辑距离如何用动态规划求解？（LeetCode 72）

简化版

编辑距离：把字符串 a 变成 b，每次可以插入、删除、替换一个字符，求最少操作次数。二维 DP：dp[i][j] = 「把 a 的前 i 个字符变成 b 的前 j 个字符的最少操作数」。当前字符相等时不用操作，dp[i][j] = dp[i-1][j-1]；不等时在替换、删除、插入三种里取最小再 +1：dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。答案 dp[m][n]。

详细版

int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;   // b 为空：删光 a 的 i 个字符
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // a 为空：插入 b 的 j 个字符
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];      // 字符相同，不操作
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],           // 替换
                                Math.min(dp[i - 1][j],              // 删除
                                         dp[i][j - 1]));            // 插入
        }
    }
    return dp[m][n];
}

状态：dp[i][j] = a[0..i-1] 转成 b[0..j-1] 的最少操作数。
相等：dp[i][j] = dp[i-1][j-1]（这对字符免操作）。
不等：1 + min(替换 dp[i-1][j-1], 删除 dp[i-1][j], 插入 dp[i][j-1])。
初始化：dp[i][0]=i、dp[0][j]=j（一方为空时，全删或全插）。
复杂度：O(m·n) 时间、O(m·n) 空间（可压到 O(n)）。

完整版教学

一、问题：增删改三种操作的最小次数

编辑距离（Levenshtein 距离）：给两个词 a、b，允许对 a 做三种操作——插入一个字符、删除一个字符、替换一个字符，问把 a 变成 b 最少要几步。例如 "horse" → "ros" 的编辑距离是 3。它是双序列 DP 里最经典也最能考察状态设计的题，广泛用于拼写纠错、DNA 序列比对、diff 工具。

二、状态定义

定义状态：dp[i][j] = 「把 a 的前 i 个字符 a[0..i-1] 转换成 b 的前 j 个字符 b[0..j-1]，所需的最少操作数」。

和 LCS 一样用前缀 + 多开一行一列的技巧：dp 大小 (m+1)×(n+1)，下标 0 表示空前缀，dp[i][j] 对应字符 a[i-1]、b[j-1]。目标是 dp[m][n]。

三、转移方程：相等继承，不等取三种操作最小 + 1

看 a 的第 i 个字符和 b 的第 j 个字符：

两字符相等（a[i-1] == 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-1],   // 替换
                    dp[i-1][j],     // 删除
                    dp[i][j-1] )    // 插入

四、三个来源分别对应替换 / 删除 / 插入（理解难点）

这一步最容易背混，务必理解每一项对应哪种操作：

dp[i-1][j-1] → 替换：把 a[i-1] 直接改成 b[j-1]，两串各消化一个字符，回到「a 前 i-1 对 b 前 j-1」，加这一次替换。
dp[i-1][j] → 删除：删掉 a 的第 i 个字符 a[i-1]，a 少一个字符（变成前 i-1），要匹配的 b 还是前 j，加这一次删除。
dp[i][j-1] → 插入：在 a 末尾插入一个 b[j-1]，a 侧 i 不变、b 侧消化掉第 j 个字符（变前 j-1），加这一次插入。

记忆窍门：下标「减谁」就对谁动手——i 减 1 是对 a 操作（删），j 减 1 是对 b 对齐（插），i、j 都减 1 是替换。三者取最小，就是当前最省的走法。

五、初始化的含义

边界要单独想清楚，它们代表「一方是空串」：

dp[i][0] = i：把 a 的前 i 个字符变成空串 b，只能一个个删，删 i 次。
dp[0][j] = j：把空串 a 变成 b 的前 j 个字符，只能一个个插，插 j 次。
dp[0][0] = 0：空变空，不用操作。

这些边界是整个递推的地基，填错会连锁出错。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。

转移过程是：末字符相等继承 dp[i-1][j-1]；否则取删除 dp[i-1][j]、插入 dp[i][j-1]、替换 dp[i-1][j-1] 的最小值加 1。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：horse→ros 的表格最终为 3：替换 h→r、删除 r、删除 e。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：第 0 行/列表示与空串互转，值分别为 j/i；若操作成本不同需分别加权；恢复操作序列要记录前驱。

核对项	本题答案
复杂度	O(mn) 时间与空间，可压成 O(min(m,n)) 但难恢复路径
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：字符不等只需考虑替换。 最优可能是插入或删除。
误区：dp[i][j] 直接对应字符下标 i、j。 它表示前缀长度，字符是 i-1、j-1。
误区：压缩空间后仍能直接恢复路径。 只保留一行会丢失完整前驱信息。
追问：删除来源为何是 dp[i-1][j]？ 先把较短的 word1 前缀变成目标，再删除当前多余字符。
追问：插入和删除是否对称？ 成本相同且交换源目标时距离对称；加权成本可能不对称。
追问：怎样输出操作过程？ 从 dp[m][n] 按等式成立的前驱逆向回溯。

九、加强记忆

编辑距离 = 插入/删除/替换把 a 变 b 的最少步数。二维 DP：dp[i][j] = a 前 i 变 b 前 j 的最少操作。字符相等 dp[i][j]=dp[i-1][j-1]（免操作）；不等 dp[i][j]=1+min(dp[i-1][j-1] 替换, dp[i-1][j] 删除, dp[i][j-1] 插入)。初始化 dp[i][0]=i（全删）、dp[0][j]=j（全插）。记「下标减谁就对谁动手」：i-1 删、j-1 插、都减替换。答案 dp[m][n]，复杂度 O(m·n)。

简化版

详细版