题解 | #最小编辑代价#

str1 ：abcd str2 ：ab
..... a b
a
b
c
d

import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here


        int n = str1.length();
        int m = str2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 0 ; i <= n; i++){
            dp[i][0] = i*dc;
        }
        for(int i = 0 ; i <= m; i++){
            dp[0][i] = i*ic;
        }
        for(int i = 1; i <= n; ++i){
            char c1 = str1.charAt(i-1);
            for(int j = 1; j <= m ;++j){
                int left = dp[i][j-1] + ic;
                int above = dp[i-1][j] + dc;
                int left_above = dp[i-1][j-1];
                if(c1 != str2.charAt(j-1)){
                    left_above = dp[i-1][j-1] + rc;
                }
                dp[i][j] = Math.min(left_above,Math.min(left,above));
            }
        }
        return dp[n][m];

    }
}