用動態(tài)規(guī)劃解題：
dp[i][j]表示word1 0 - i 與word2 0 - j 的edit distance尤莺。
當(dāng)增加的如果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];
}
