题解 | #最小编辑代价#

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

        vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0));

        for(int i =0; i<=str2.size();i++){
            dp[0][i] = ic*i;//注意这个是增加
        }

        for(int i =0; i<=str1.size();i++){
            dp[i][0] = dc*i;//这个是减少，因为我们要匹配后面得。
        }

        for(int i =1; i<=str1.size();i++){
            for(int j=1; j<=str2.size();j++){

                int r=0;

                if(str1[i-1]!=str2[j-1]){
                    r = rc;
                }

                dp[i][j] = min(dp[i-1][j]+dc,min(dp[i][j-1]+ic,dp[i-1][j-1] + r));
            }
        }

        return dp[str1.size()][str2.size()];
    }
};