最小编辑代价-动态规划

    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int len1 = str1.length(), len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        // 计算编辑的最小次数
//         for (int i=0;i<=len1;++i){
//             for (int j=0;j<=len2;++j){
//                 if (i == 0 || j == 0){
//                     dp[i][j] = Math.max(i, j);
//                 }else{
//                     if (str1.charAt(i-1) == str2.charAt(j-1)){
//                         dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j])+1, dp[i-1][j-1]);
//                     }else{
//                         dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j])+1, dp[i-1][j-1]+1);
//                     }
//                 }
//             }
//         }
        // 计算编辑的最小代价
        for (int i=0;i<=len1;++i){
            for (int j=0;j<=len2;++j){
                if (i == 0){
                    dp[i][j] = j*ic;
                }else if (j == 0){
                    dp[i][j] = i*dc;
                }else{
                    if (str1.charAt(i-1) == str2.charAt(j-1)){
                        dp[i][j] = Math.min(Math.min(dp[i][j-1]+ic, dp[i-1][j]+dc), dp[i-1][j-1]);
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i][j-1]+ic, dp[i-1][j]+dc), dp[i-1][j-1]+rc);
                    }
                }
            }
        }
        return dp[len1][len2];
    }