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];}
}