一.题目
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二.解体思路
这一道题读完之后感觉很复杂，完全不知道怎么入手。如果从动态规划的角度考虑。我们看到这个题目中有两个字符串，想到是不是可以用一个二维数组作为dp。dp的长和宽就是两个字符串的长度。那么dp[i][j]表达什么含义呢？因为要求的是word1转换为word2的步骤。那么它的子问题可以为word1的前i个字符转换为word2的前j个字符。这也就是dp[i][j]的含义。
定义出问题来，之后就是找递推公式和初始化了。
先考虑递推公式。一般来说dp[i][j]经常由dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]来推导出来。对于这道题适不适用呢？答案是肯定的。可以按word1[i]是否和word2[j]相等来分为两种情况讨论。
总结：这一题属于用二维数组作为dp数组的题目。关键是dp[i][j]可以用d[i-1][j-1]等可以推导出来。题目为变量1的前i个字符转换为变量2的前j个字符。与这一题类似的还有
三.AC代码
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length(),m = word2.length();
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 0;
for(int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for(int j = 1; j <= m; j++) {
dp[0][j] = j;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1] - 1);
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
}
