题解 | #最小编辑代价#（动态规划）

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));
        for(int i = 1; i <= m; i++) dp[i][0] = i * dc;
        for(int j = 1; j <= n; j++) dp[0][j] = j * ic; // 初始化

        for(int i = 1; i <= m; i++){
            char c1 = str1[i-1];
            for(int j = 1; j <= n; j++){
                char c2 = str2[j-1];
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int insert = dp[i][j-1] + ic;
                    int dele = dp[i-1][j] + dc;
                    int replace = dp[i-1][j-1] + rc;
                    dp[i][j] = min(replace, min(dele, insert));
                }
            }
        }
        return dp[m][n];
    }
};