给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
解
对于输出长度为m和n的2个字符串，申请一个大小为(m+1)*(n+1)的数组保留每一步的结果，数组的第0行和第0列依次递增，相当于空字符串转和长度为i的字符串的编辑距离。对于dp[i][j],如果第i和第j的字符不相等，则dp[i-1][j]表示插入一个字符，dp[i][j-1]表示删除一个字符，di[i-1][j-1]表示替换字符，dp[i][j]取3者最小值。
public static int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if(0==m*n)
return Math.max(m, n);
int[][] dp = new int[m+1][n+1];
for(int i=0;i<m+1;i++)
dp[i][0] = i;
for(int i=0;i<n+1;i++)
dp[0][i] = i;
for(int i=1;i<m+1;i++)
for(int j=1;j<n+1;j++) {
int left = dp[i-1][j]+1,up = dp[i][j-1]+1,left_up = dp[i-1][j-1];
if(word1.charAt(i-1)!=word2.charAt(j-1))
left_up++;
dp[i][j] = Math.min(left, Math.min(up,left_up));
}
return dp[m][n];
}
