LeetCode72编辑距离（动态规划）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution” 输出：5 解释： intention -> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

提示：

0 <= word1.length, word2.length <= 500 word1 和 word2 由小写英文字母组成

看到要求最少的操作数，可以基本判定是用动态规划，而且还是二维的，因为有两个字符串，那就有两个长度，一维肯定是表示不了的，dp[i][j]就表示将长度为i的word1转换为长度为j的word2所需的最少操作数。状态表示很容易，麻烦一点的就是状态计算，我们该怎样划分子问题大的分类可以分成两种，那就是我们是否需要进行操作，如果我们的两个字符串结尾相同，那是不是就不用进行操作，直接dp[i][j] = dp[i - 1][j - 1]，沿用它的上一种状态就好了第二类就是我们要进行操作，但操作又分成三种，我们还要进行讨论。 第一种：插入一个字符，我们可以将word2末尾的字符插入到word1末尾，那么现在两个字符串的末尾相同，就回到了我们的第一大类第二种：删除一个字符，那么我们只需要管dp[i - 1][j]的大小就可以了，这个比较好理解第三种：替换一个字符，同样是将两个字符串的末尾变成了一样的，变成了第一大类 思路已经出来了，接下来就是代码的实现 class Solution { public int minDistance(String word1, String word2) { int n = word1.length(), m = word2.length(); int dp[][] = new int[n + 1][m + 1]; // 这里需要进行初始化，模拟有一个串长度为0的情况 for (int i = 0; i <= n; i++) { dp[i][0] = i; } for (int j = 0; j <= m; j++) { dp[0][j] = j; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // 因为我们是从1开始遍历的，所以第i个数是word1.charAt(i - 1) if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j -1], Math.min(dp[i - 1][j], dp[i][j -1])) + 1; } } } return dp[n][m]; } }

本题到这里就结束了，这个其实还是有一些难度的，不懂的话可以留言