1. 插入： dp[i][j-1] + ic 表示在str1的前i位转化成str2的前j-1个位 代价最小的基础上，将str2的第j位添加到str1上
2. 删除： dp[i-1][j] + dc 表示在str1的前i-1位转化成str2的前j个位 代价最小的基础上，将str1的第i位删除
3. 修改： dp[i-1][j-1] + dc 表示在str1的前i-1位转化成str2的前j-1个位 代价最小的基础上，修改str1的第i位使其等于str2的第j位

class Solution {
public:
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int len1=str1.size();
        int len2=str2.size();
        //dp[i][j]表示将str1[i]变化成str2[j]所需要的最小操作数
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i=0;i<=len1;i++){
            dp[i][0]=i*dc;//第二个字符串为空时，第一个字符串每多一位，第一个字符串删除一位
        }
        for(int i=0;i<=len2;i++){
            dp[0][i]=i*ic;//第一个字符串为空时，第二个字符串每多一位，第一个字符串添加一位
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1];//当str1的第i个位置的元素和str2第j个位置的元素相同时
                }else{//不同时分情况，要选择最小的情况
                    int ins=dp[i][j-1]+ic;//表示在str1的前i个字符变成str2的前j-1个字符操作数最小的基础上，把str2的第j位字符添加到str1上
                    int del=dp[i-1][j]+dc;//表示在str1的前i-1个字符变成str2的前j个字符操作数最小的基础上，删除str1的第i个字符
                    int rep=dp[i-1][j-1]+rc;//表示在str1的前i-1个字符变成str2前j-1个字符操作数最小的基础上修改str1的第i位使其等于str2的第j位
                    dp[i][j]=min(ins,min(del,rep));
                }
            }
        }
        return dp[len1][len2];
    }
};