最小编辑代价

参考链接：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
我们可以对任意一个单词进行三种操作：
在单词 A 中插入一个字符；
在单词 A 中插入一个字符；
修改单词 A 的一个字符。
我们说word1和word2的编辑距离为X，意味着word1经过X步，变成了word2，咋变的你不用管，反正知道就需要X步，并且这是个最少的步数。
有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。
当我们获得 D[i][j-1]，D[i-1][j] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。

1. D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i][j-1] + ic；
2. D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，即删除A的末尾元素，那么 D[i][j] 最小可以为 D[i-1][j] + dc；
3. D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 D[i][j] 最小可以为 D[i-1][j-1] + rc。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。

   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整型
    参考链接：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
    */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int n=str1.size(),m=str2.size();
        //str1为空串
        if(n==0)return ic*m;
        if(m==0)return dc*n;
        vector<vector<int>>dp(n+1,vector<int>(m+1));//定义编辑代价矩阵
        //定义边界条件
        for(int i=0;i<n+1;i++){
            dp[i][0]=dc*i;
        }
        for(int j=0;j<m+1;j++){
            dp[0][j]=ic*j;
        }
        //计算剩余的编辑代价矩阵
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;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]+dc,min(dp[i][j-1]+ic,dp[i-1][j-1]+rc));
            }
        }
        return dp[n][m];
    }
   };