leetcode 72. 编辑距离

注意点:1,0行，0列，空位置必须留下来2、红色位置

class Solution {
    public int minDistance(String word1, String word2) {
        /*
        策略：dp[i][j]为从str1(0~i-1)变为str2(0~j-1)的最小成本,行列第一个为空！
        */
        int l1=word1.length();
        int l2=word2.length();
        char[] chas1=word1.toCharArray();
        char[] chas2=word2.toCharArray();                                              
        int[][] dp=new int[l1+1][l2+1];//
        dp[0][0]=0;
        for(int i=1;i<=l1;i++){
            dp[i][0]=i;
        }
        for(int i=1;i<=l2;i++){
            dp[0][i]=i;
        }
        //一般情况，最后一位相等，与都减一位相同。否则，都减一位替换。当然，也有可能别的更小，(i-1,j)删除一个，(i,j-1)插入一个
        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                if(chas1[i-1]==chas2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                dp[i][j]=Math.min( dp[i][j],dp[i-1][j]+1);
                dp[i][j]=Math.min( dp[i][j],dp[i][j-1]+1);
            }
        }   
        return dp[l1][l2];
    }
}