题解 | #最小编辑代价#

动态规划：
首先生成一个大小为（M+1）X（N+1）的矩阵dp，dp[i][j]的值代表str1[0..i-1]编辑成str2[0..j-1]的最小代价。

public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        if (str1 == null || str2 == null){
            return 0;
        }
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
        int row = cs1.length + 1;
        int col = cs2.length + 1;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            dp[i][0] = dc * i;
        }
        for (int i = 0; i < col; i++) {
            dp[0][i] = ic * i;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (cs1[i-1] == cs2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = dp[i-1][j-1] + rc;
                }
                dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);
            }
        }
        return dp[row-1][col-1];
    }