题解 | #最小编辑代价#

思路

1、动态规划问题，dp[i][j]代表前i个转化到前j个的代价（第i个代表下标为i-1的字符）
2、初始化第0行、第0列（边界条件）
3、递推公式：当str1[i-1] == str2[j-1]时，dp[i][j] == dp[i-1][j-1]; 当不想等时，取三个情况的最小值
4、返回dp[m][n]，代表str1的前m个转换为str2的前n个的代价。

代码

class Solution {
public:
    /**
     * 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整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.size();
        int n = str2.size();
        // dp数组，dp[i][j]代表将str1[i]变为str2[j]的代价
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        dp[0][0] = 0;
        for(int i = 1; i<=m; i++){
            dp[i][0] = i*dc;
        }
        for(int j = 1; j<=n; j++){
            dp[0][j] = j*ic;
        }

        for(int i = 1; i<=m; i++){
            for(int j = 1; j<=n; j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j] = dp[i-1][j-1];

                }
                else{
                    int cost1 = dp[i][j-1]+ic;
                    int cost2 = dp[i-1][j]+dc;
                    int cost3 = dp[i-1][j-1]+rc;
                    dp[i][j] = min(min(cost1, cost2), cost3);
                }
            }
        }

        return dp[m][n];
    }
};