题解 | #最小编辑代价#

编辑距离变型题
设表示将的前个元素转换成的前个元素的最小代价，状态转移方程：
（1）；//啥都不操作；
（2）,

时间复杂度：
空间复杂度：

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.length(), n = str2.length();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        //边界
        for(int i = 1; i <= m; i ++) dp[i][0] = dp[i - 1][0] + dc;
        for(int j = 1; j <= n; j ++) dp[0][j] = dp[0][j - 1] + ic;
        //dp
        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 dp[i][j] = min({dp[i - 1][j - 1] + rc,
                                     dp[i][j - 1] + ic,
                                     dp[i - 1][j] + dc});
            }
        }
        return dp[m][n];
    }
};