题解 | #最小编辑代价#

题解一：动态规划
动态转移方程分析图示：

复杂度分析：
时间复杂度：O(MN)
空间复杂度：O(MN)

实现如下:

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 len1 = str1.size();
        int len2 = str2.size();
        int dp[len1+1][len2+1];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i<=len1;i++) dp[i][0] =i*dc;  // str2 长度为0，只能删除
        for(int i = 1;i<=len2;i++) dp[0][i] = i*ic; // str1 长度为0， 只能插入
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j<=len2;j++){
                if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1];  //r1[i] = str2[j]
                else {
                    dp[i][j] = min(dp[i-1][j-1]+rc,dp[i][j-1]+ic);   //dp[i][j] 取三种措施的最小的代价
                    dp[i][j] = min(dp[i][j],dp[i-1][j]+dc);
                }
            }
        }
        return dp[len1][len2];
    }
};

题解二：滚动数组优化空间复杂度
优化思路： dp[i][j]是从dp[i][j-1]、dp[i-1][j]、dp[i-1][j-1] 转移过来的。 将dp数组变为一维数组之后，那么dp[i][j-1],dp[i-1][j-1]都用dp[j-1]表示，这就造成了冲突。所以使用pre表示dp[i-1][j-1],dp[j-1] = dp[i][j-1],dp[j]表示上一轮的值
复杂度分析：
时间复杂度：O(NM)
空间复杂度: O(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) {
            int len1 = str1.size();
            int len2 = str2.size();
            int dp[len2+1];
            memset(dp,0, sizeof(dp));
            //初始化第一行
            for(int i = 1;i<=len2;i++) dp[i] = i*ic;
            for(int i = 1;i<=len1;i++){
                int pre = dp[0];
                dp[0] = i*dc;
                for(int j = 1;j<=len2;++j){
                    int tmp = dp[j];  // 上一轮的dp[i-1][j]
                    if(str1[i-1]==str2[j-1]) dp[j] = pre;
                    else  dp[j] = min(pre+rc,min(dp[j-1]+ic,tmp+dc));
                     pre = tmp;//更新dp[i-1][j-1]
                }
        }
        return dp[len2];
    }
};