1.经典动态规划解法

设s[k]为s[0...k]的子串，那么cost[i][j]为从s1[i]编辑为s2[j]的代价。

• 如果s1[i] == s2[j]， 那么cost[i][j] = cost[i-1][j-1];
• 否则有三种方法可以完成这一次编辑:：

  • 用cost[i-1][j-1]的代价将s1[i-1]编辑为s2[j-1],再将s1[i]替换为s[j]，即cost[i][j-1] + rc;

  • 用cost[i][j-1]的代价将s1[i]编辑为s2[j-1],再插入一个s2[j]字符, 即cost[i][j-1] + ic;

  • 用cost[i-1][j]的代价将s1[i-1]编辑为s2[j], 再删除s1[i]字符，即cost[i-1][j] + dc;

  • 所以最小编辑代价，cost[i][j] = min(cost[i-1][j-1] + rc, cost[i][j-1] + ic, cost[i-1][j] + dc);

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 n1 = str1.size();
        int n2 = str2.size();
        vector<vector<int>> cost(n1 + 1, vector<int>(n2 + 1 ));
        for(int i = 0; i < n1 + 1; ++i){
            cost[i][0] = i*dc;
        }
        for(int j = 0; j < n2 + 1; ++j){
            cost[0][j] = j*ic;
        }
        
        for(int i = 1; i < n1 + 1; ++i){
            for(int j = 1; j < n2 + 1; ++j){
                if(str1[i-1] == str2[j-1]){
                    cost[i][j] = cost[i-1][j-1];
                }else{
                    cost[i][j] = min(min(cost[i-1][j] + dc, cost[i][j-1] + ic),  cost[i-1][j-1] + rc);
                }
            }
        }
        return cost[n1][n2];
    }
};

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

2. 空间优化

每一个位置[i，j]只与[i-1,j-1]、[i-1,j]、[i,j-1]三个位置有关。[i-1,j-1]为左上对角线上的位置，只需用一个变量pre保存；[i-1][j]为当前列的上一行的位置，[i][j-1]当前行的前一列的位置，只需用一个数组保存。

行i从上至下扫描;列j从左到右扫描。使用cost[j]保存扫描到j列时的编辑代价，此时，cost[0...j]为当前行更新到第j列已更新的值，cost[j+1:n2]为上一行相应位置的代价，还需要更新。

• cost[j]的初始值为空串“”编辑为s2[j]的代价，即ic*j;
• cost[0]为将s1[i]编辑为空串“”的代价，即dc*i。
• pre的初值为cost[0]
• 用tmp保存cost[j]更新前的值(即上一行的cost[j])，用作下一列更新的pre值。

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 n1 = str1.size();
        int n2 = str2.size();
        vector<int> cost(n2+1);
        for(int j = 1; j < n2 + 1; j++){
            cost[j] = j*ic;
        }
        for(int i = 1; i < n1 + 1; i++){
            int pre = cost[0];
            cost[0] = dc*i;
            for(int j = 1; j < n2 + 1; j++){
                int tmp = cost[j]; //保存更新cost[j]之前的值，用作下一次更新的pre。
                if(str1[i-1] == str2[j-1]){
                    cost[j] = pre;
                }else{
                    cost[j] = min(cost[j-1] + ic, cost[j] + dc);
                    cost[j] = min(cost[j], pre + rc);
                }
                pre = tmp;
            }
        }
        
        return cost[n2];
    }
};

分析：时间复杂度O(nm),空间复杂度O(n).