用动态规划解题：
dp[i][j]表示word1 0 - i 与word2 0 - j 的edit distance。
当增加的如果word 1[i] == word2[j]则 dp[i+1][j+1] = dp[i][j];
如果不一样则可以通过三种方式一样 insert replace delete
delete： 则是dp [i+1][j+1] = dp[i][j+1] + 1 (word2的index增加了一个i却没有增加)
replace ： 则是dp [i+1][j+1] = dp[i][j] + 1
insert ： 则是dp [i+1][j+1] = dp[i+1][j] + 1
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
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++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else {
dp[i][j] = 1 + Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]));
}
}
}
return dp[m][n];
}
