给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
思路：
刚拿到题目没什么头绪，但是可以确定的是动态规划的做法，重要的是如何实现
建立dp【i】【j】是从word1的前 i 个到word2的前 j 个需要最短操作次数
往下就是推递推公式的事情
详细见代码及注释
复杂度：public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int dp[][] = new int[m+1][n+1];
//初始化，倘若word1前i个为空或者word2前j个为空
//word2什么都没有，那就是全部都删除，有多少个删多少个
for(int i=0;i<=m;++i){
dp[i][0] = i;
}
//word1什么都没有，那就是全部都靠增加，word2有多少个就增加多少个
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){
//word1靠增删改去匹配word2
//word1如果要增 ，即 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
dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
//如果两字母相同，就是前一个的
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
时间复杂度：O(nm)
空间复杂度：O(mn)
代码：
