动态规划困难1 种解法

#72编辑距离

计算把 word1 转换为 word2 所需的最少插入、删除或替换次数。

#字符串#动态规划

解题主线

dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数。

末字符相同则直接继承 dp[i - 1][j - 1]；否则从替换、删除、插入三个前驱状态中取最小值再加一。

额外的第 0 行和第 0 列表示空串，使边界分别初始化为连续插入和连续删除的次数。

解法 1：二维前缀动态规划

按前缀长度从小到大填表，为每对前缀选择末字符匹配或三种编辑操作中的最优转移。

时间复杂度

O(mn)，m、n 分别为两个字符串长度

空间复杂度

O(mn)

72. 编辑距离 · 二维前缀动态规划

java

final class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            throw new IllegalArgumentException("words must not be null");
        }

        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int replace = dp[i - 1][j - 1];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    dp[i][j] = Math.min(replace, Math.min(delete, insert)) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

按前缀长度从小到大填表，为每对前缀选择末字符匹配或三种编辑操作中的最优转移。

边界与易错点

字符串下标是 i - 1、j - 1，而 DP 下标是前缀长度 i、j，不能混用。
dp[i - 1][j] 对应删除 word1 末字符，dp[i][j - 1] 对应向 word1 插入 word2 末字符。
两个末字符相等时不需要加一，否则会高估答案。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/zhard/Q072_char_distance.java