题解 | #最小编辑代价#

动态规划，插入、删除和替换的代价是不同的。注意题意只能编辑str1。dp[i][j]表示以i-1结尾的str1，和以j-1结尾的str2之间的最小编辑距离。初始化dp的时候只能插入或删除str1，更新dp数组时选择插入、删除、替换的最小值。

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) {
        int m=str1.size();
        int n=str2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[0][0]=0;
        for(int j=1;j<=n;j++) dp[0][j]=ic*j;
        for(int i=1;i<=m;i++) dp[i][0]=dc*i;
        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 min_ic=dp[i][j-1]+ic;
                    int min_dc=dp[i-1][j]+dc;
                    int min_rc=dp[i-1][j-1]+rc;
                    dp[i][j]=min(min_ic,min(min_dc,min_rc));
                }
            }
        }
        return dp[m][n];
    }
};