题解 | #编辑距离(二)#

class Solution {
public:
    int dp[5005][5005]={0};//dp[i][j]表示将字符串str1的前i个字符编辑成字符串str2的前j个字符的最小代价
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int n1=str1.size(),n2=str2.size();
        memset(dp,0x3f,sizeof(dp));//初始化
        dp[0][0]=0;
        for(int i=1;i<=n1;i++){//删除代价
            dp[i][0]=i*dc;
        }
        for(int i=1;i<=n2;i++){//插入代价
            dp[0][i]=i*ic;
        }
        
        for(int i=1;i<=n1;i++){//二重循环
            for(int j=1;j<=n2;j++){
                if(str1[i-1]==str2[j-1]){//如果相等，则dp[i][j]=dp[i-1][j-1]
                    dp[i][j]=dp[i-1][j-1];
                }else{//否则，取插入、删 除和替换代价的最小值
                    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+rc);//替换代价
                    dp[i][j]=min(dp[i][j],dp[i][j-1]+ic);//插入代价
                    dp[i][j]=min(dp[i][j],dp[i-1][j]+dc);//删除代价
                }
            }
        }
        return dp[n1][n2];
    }
};