描述

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

类似题目：编辑距离(一)：插入、删除、替换代价相等

思路1：动态规划

示例

假设ic=dc=rc=1，将字符串horse转成字符串ros（盗一下网上的图）

1. 第一列表示horse转成空字符串的代价，需要删除i个字符
2. 第一行表示空字符串转成ros的代价，需要插入j个字符
3. 每一个位置的值由周围三个位置决定：dp[i][j] = min(dp[i-1][j-1] + rc, dp[i][j-1] + ic, dp[i-1][j] + dc)
   1. 例如h编辑为r，代价为1：dp[0][0] + rc = 1
   2. h编辑为ro，代价为2：dp[0][1] + rc = 2或者dp[1][1] + ic = 2
   3. h编辑为ros，代价为3：dp[0][2] + rc = 3或者dp[1][2] + ic = 3
   4. horse编辑为ros，代价为3：dp[4][3] + dc = 3，即先将hors转为ros，再删除一个字符

总结

dp[i][j]表示str1[0~i]编辑成str2[0~j]的最小代价，假设不包含i、j（即右侧为开区间）

边界情况：

1. dp[0][0]=0：空串编辑成空串的代价为0
2. dp[0][j]=j*ic：把一个空串编辑成str2[0~j]的代价，将j个字符全部插入
3. dp[i][0]=i*dc：把str1[0~i]编辑成空串的代价，将i个字符全部删除

如果最后一个字符相同str1[i] == str2[j]，则只需要将str1[0~i-1]编辑成str2[0~j-1]：dp[i][j] = dp[i-1][j-1];

如果最后一个字符不同str1[i-1] != str2[j-1]，有三种情况：选择代价最小的一种情况

1. 先把str1[0~i-1]编辑成str2[0~j-1]，再替换最后一个字符：dp[i][j] = dp[i-1][j-1] + rc;
2. 先把str1[0~i]编辑成str2[0~j-1]，再插入一个字符：dp[i][j] = dp[i][j-1] + ic;
3. 先把str1[0~i-1]编辑成str1[0~j]，再删除一个字符：dp[i][j] = dp[i-1][j] + dc;

public class Solution {
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        int len1 = str1.length();
        int len2 = str2.length();
        //dp[i][j]不包含第i个字符和第j个字符，因此需要+1
        int[][] dp = new int[len1+1][len2+1];
        //矩阵第一行表示空字符串转为str2的代价，插入j个字符
        for(int j = 1; j <= len2; j++) {
            dp[0][j] = j * ic;
        }
        //矩阵第1列表示str1转为空字符串的代价，删除i个字符
        for(int i = 1; i <= len1; i++) {
            dp[i][0] = i * dc;
        }
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i][j-1] + ic, dp[i-1][j] + dc);
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + rc);
                }
            }
        }
        return dp[len1][len2];
    }
}