这个题目
动态规划思路：
1.状态定义：str1前i个字符编辑成str2前j个字符的最小代价为dp[i][j]
2.初始状态：
    1.str1前0个字符编辑str2前j个字符的最小代价是ic * j,因为空串转其他字符串只能插入其他的字符，需要插入j次
    2.str1前i个字符编辑str2前0个字符的最小代价是dc * i,因为字符串转空串只能删除字符，需要插入i次
3.转移方程：
    1.str1第i个字符跟str2的第j个字符相等：把str1前i-1个字符变成str2的前j-1个字符就可以了，因为最后一个字符相等。故：dp[i][j] = dp[i-1][j-1]
    2.str1第i个字符跟str2的第j个字符不相等：
               1.替换str1最后一个字符，只需要str1前i-1个字符变成str2的前j-1个字符，然后加上一个替换rc就可以了。dp[i-1][j-1]+rc
               2.插入str1最后一个字符，只需要str1前i个字符变成str2的前j-1个字符，然后加上一个替换ic就可以了。dp[i][j-1]+ic
               3.删除str1最后一个字符，只需要str1前i-1个字符变成str2的前j个字符，然后加上一个替换dc就可以了。dp[i-1][j]+dc
        最小代价，三者取min    
dp[i][j] = min(min(dp[i-1][j-1]+rc,dp[i-1][j]+dc),dp[i][j-1]+ic);

 
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
        int m=str1.size();
        int n=str2.size();
        int dp[m+1][n+1];
        for(int i=0;i<=m;i++){
           dp[i][0] = i * dc;
        }
         
        for(int i=0;i<=n;i++){
            dp[0][i] = i * 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{
                    dp[i][j] = min(min(dp[i-1][j-1]+rc,dp[i-1][j]+dc),dp[i][j-1]+ic);
                }
                 
            }
        }
        return dp[m][n];
    }
};
空间优化，由于都只是使用前一层的数据，即dp[i-1][?]层的数据，那么dp[0][?]~dp[i-2][?]的数据无需保存。
可以使用滚动数据优化。
   可以使用dp[j]代替dp[i-1][j]
   但是有一个冲突dp[i-1][j-1],dp[i][j-1],故需要定义个变量来存储其中一个。
   还有一个初始化的问题dp[0],代表dp[?][0]，因此每个循环需要重新赋值：str1前i个字符编辑str2前0个字符的最小代价是dc * i 
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
        int m=str1.size();
        int n=str2.size();
        int dp[n+1];
        
        for(int i=0;i<=n;i++){
            dp[i] = i * ic;
        }
        for(int i=1;i<=m;i++){
            int pre = dp[0]; //dp[i-1][j-1]
            dp[0] = i*dc; //dp[i-1][0]
            for(int j=1;j<=n;j++){
                int tmp = dp[j];  // 上一轮的dp[i-1][j]
                if(str1[i-1] == str2[j-1]){
                    dp[j] = pre;//dp[i-1][j-1]
                }else{
                    //dp[j-1]-> dp[i][j-1]
                    dp[j] = min(min(pre+rc,tmp+dc),dp[j-1]+ic);
                }
                pre = tmp;//dp[i-1][j-1]
            }
        }
        return dp[n];
    }
};