题解 | #编辑距离#动态归划

 可用二维数组i,j表示从word1的前i个字符到word2的前j个字符 dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。
状态公式： 有两种情况：  1.当第i个字符和第j个字符相等时，那么从i到j的最小编辑距离只需要计算前i-1个字符到前j-1个字符的最小编辑距离===》》if（str1[i-1]==str2[j-1],dp[i][j]=dp[i-1][j-1]; 2.当他们不相等时，那么就可以通过删除，增加，替换来变换，只需要计算三者中的最小值即可： (可以利用前面字符串计算出来的最小切割距离再加上最后一步的删除/替换/增加操作)  dp[i][j]=dp[i-1][j-1]+1          word1的前i-1个字符到word2的前j-1个字符所需编辑距离+1（替换）  dp[i][j]=dp[i][j-1]              word1的前i个字符到word2的前j-1个字符所需编辑距离+1（增加）  dp[i][j]=dp[i-1][j]              word1的前i-1个字符到word2的前j个字符所需编辑距离+1（删除） 

public class EditDistance {
    public static int minDistance (String word1, String word2){
        int n=word1.length();
        int m=word2.length();
        int[][] dp=new int[n+1][m+1];//存储word1的前i个字符变成word2的前j个字符所需要的最小编辑距离
        char[] str1=word1.toCharArray();//将word1和word2转化为数组
        char[] str2=word2.toCharArray();
        for(int i=0;i<=n;i++) dp[i][0]=i;//遍历word1字符串，由word1的前i个字符变成word2的空串最小编辑距离是i
        for(int j=0;j<=m;j++)  dp[0][j]=j;//遍历word2字符串，由word1的空串变成word2的前j个字符最小编辑距离是j
        for(int i=1;i<=n;i++){//从第一个字符开始
            for(int j=1;j<=m;j++){
                if(str1[i-1]==str2[j-1]){//第i和第j个字符的在字符数组的下标是i-1和j-1,如果他们相等那么最小编辑距离就是前面一个字符的最小编辑距离
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j-1]+1,dp[i][j-1]+1),dp[i-1][j]+1);//如果第i个字符和第j个字符不相等，那么最小编辑距离就是增加，删除，替换的最小值
                }
            }
        }
        return dp[n][m];
    }
}