95、动态规划-编辑距离

递归暴力解法

递归方法的基本思想是考虑最后一个字符的操作，然后根据这些操作递归处理子问题。

递归函数定义：定义一个递归函数 minDistance(i, j)，表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。

递归终止条件：

• 如果 i == 0，意味着 word1 为空，此时将 word1 转换成 word2 的前 j 个字符就需要 j 次插入操作。
• 如果 j == 0，意味着 word2 为空，此时将 word1 的前 i 个字符转换成空字符串需要 i 次删除操作。

递归转移方程：

• 如果 word1[i-1] == word2[j-1]，则当前两个字符相等，不需要操作，所以 minDistance(i, j) = minDistance(i-1, j-1)。
• 如果不相等，则可以进行插入、删除或替换操作，转移方程为：
  • 插入：minDistance(i, j) = minDistance(i, j-1) + 1
  • 删除：minDistance(i, j) = minDistance(i-1, j) + 1
  • 替换：minDistance(i, j) = minDistance(i-1, j-1) + 1
• 取三者的最小值。

代码如下：

public class Solution {
    // 主方法，用于外部调用，传入两个字符串
    public int minDistance(String word1, String word2) {
        // 调用递归助手函数，初始化i和j为字符串的长度，从字符串尾部开始比较
        return minDistanceHelper(word1, word2, word1.length(), word2.length());
    }

    // 递归助手函数，用于计算两个字符串的最小编辑距离
    private int minDistanceHelper(String word1, String word2, int m, int n) {
        // 如果第一个字符串为空，则转换的代价是第二个字符串的长度（即插入n次）
        if (m == 0) return n;
        // 如果第二个字符串为空，则转换的代价是第一个字符串的长度（即删除m次）
        if (n == 0) return m;

        // 如果两个字符串的当前字符相等，则不需要操作，递归考虑前一个字符
        if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
            return minDistanceHelper(word1, word2, m - 1, n - 1);
        }

        // 计算插入操作的代价：将word2的第n个字符插入到word1的末尾，然后继续处理剩余的字符串
        int insert = minDistanceHelper(word1, word2, m, n - 1) + 1;
        // 计算删除操作的代价：删除word1的第m个字符，然后继续处理剩余的字符串
        int delete = minDistanceHelper(word1, word2, m - 1, n) + 1;
        // 计算替换操作的代价：将word1的第m个字符替换为word2的第n个字符，然后继续处理剩余的字符串
        int replace = minDistanceHelper(word1, word2, m - 1, n - 1) + 1;

        // 返回三种操作中的最小值，即为到当前位置为止的最小编辑距离
        return Math.min(Math.min(insert, delete), replace);
    }
}

但是重复计算效率很慢，改成动态规划：

动态规划方法

动态规划方法的核心思想是使用一个二维数组 dp 来存储中间结果，其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。通过填充这个数组，我们可以逐步构建出从一个空字符串到完整 word2，再从完整 word1 到 word2 的转换路径。

初始化：

• dp[0][j]：将空字符串转换为 word2 的前 j 个字符，需要 j 次插入操作。
• dp[i][0]：将 word1 的前 i 个字符转换为空字符串，需要 i 次删除操作。

状态转移方程：

• 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]，因为最后一个字符已经匹配，不需要额外操作。
• 如果 word1[i-1] != word2[j-1]，则可以从以下三个可能的操作中选择最小成本的：
  • 插入：dp[i][j] = dp[i][j-1] + 1
  • 删除：dp[i][j] = dp[i-1][j] + 1
  • 替换：dp[i][j] = dp[i-1][j-1] + 1

代码如下：

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化dp数组
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;  // 从word1的i字符变为空字符串
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;  // 从空字符串变为word2的j字符
        }

        // 填充dp数组
        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 {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}