题解 | #最小编辑代价#

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 l1 = str1.size(), l2 = str2.size();
        int f[l1 + 1][l2 + 1]; // 状态表示，f[i][j]表示str1前i个元素变成str2前j个元素所需要的最小代价
        f[0][0] = 0;
        for(int i = 1; i <= l2; i++) // 当str1增加元素所需代价
            f[0][i] = i * ic;
        for(int i = 1; i <= l1; i++) // 当str1删除元素所需代价
            f[i][0] = i * dc;

        for(int i = 1; i <= l1; i++)
            for(int j = 1; j <= l2; j++) {
                if(str1[i-1] == str2[j-1]) // 第i个元素和第j个元素在[i-1]和[j-1]处
                    f[i][j] = f[i-1][j-1];
                else {
                    int insert = f[i][j-1] + ic; // 比较str1需要删除和增加元素所需代价
                    int dele = f[i-1][j] + dc; 
                    int replace = f[i-1][j-1] + rc; // 比较替换元素所需代价
                    f[i][j] = min(insert, min(dele, replace));
                }
            }
        return f[l1][l2];
    }
};