DP

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.length(), n = str2.length();
        // str1[0, i - 1] -> str2[0, j - 1] 最小代价
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0x7FFFFFFF));
        dp[0][0] = 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)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(str1[i - 1] == str2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    int _ic = dp[i][j - 1] + ic;
                    int _dc = dp[i - 1][j] + dc;
                    int _rc = dp[i - 1][j - 1] + rc;
                    dp[i][j] = min(min(_ic, _dc), _rc);
                }
            }
        }
        return dp[m][n];
    }
};