72.Edit distance
Description
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
这道题要求求解两个字符串之间的编辑距离，也就是通过增删改，最少多少次才能把一个字符串转换为另一个字符串。
对于这种对字符串进行修改还要求极值的题目，一般使用动态规划来解决，需要解决的是动态规划过程中的状态方程。
依然用i，j两个变量代表当前需要判断的字符串长度，如果两个字符串i-1和j-1位置上的字符相同，则不需要进行修改，即dp[i][j]=dp[i-1][j-1]
如果不匹配，则需要考虑增删改三个操作分别的代价。
考虑增加，如果需要在前一个字符串第i位增加一个字符串，使其与第二个字符串相同，则需要的步数是：dp[i][j-1]+1，也就是取决于将长为i的字符串与长为j-1的字符串相匹配的修改次数+一次增加
考虑删除，如果需要删除第i位的字符使其与第二个字符串相同，则需要的步数是：dp[i-1][j]+1，与增加同理
考虑替代，如果需要将第i位的字符替代，使其与长为j的字符串相同，只需要考虑前i-1，j-1的修改次数+1即可
之后选出代价最小的方式即可。
状态方程梳理清楚后，就很容易写出代码了，需要注意的是在对第一行第一列进行初始化时，略有不同
代码如下：
class Solution {
public int minDistance(String word1, String word2) {
int [][]dp=new int[word1.length()+1][word2.length()+1];
for(int i=0;i<=word1.length();++i){
for(int j=0;j<= word2.length();++j){
if(i==0||j==0){
dp[i][j]=i+j;
}
else{
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else{
int replace=dp[i-1][j-1];
int delete=dp[i-1][j];
int insert=dp[i][j-1];
dp[i][j]=Math.min(Math.min(replace,delete),insert);
dp[i][j]++;
}
}
}
}
return dp[word1.length()][word2.length()];
}
}