参考链接：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];
 }
};