题解 | 最小编辑代价

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        //原版的编辑代价的基础上每个操作加入的权重，修改一下状态转移方程即可
        //注意边界条件也有所变化
        //仍然使用一行数组和一个额外空间记录左上位置即可
        vector<int>dp(m+1);
        //初始化要注意
        for(int i=0 ;i<=m; i++)
            dp[i]=i*c0;//只能全部增加
        //循环处理
        for(int i=1; i<=n; i++)
        {
            int prev=dp[0];//记录左上位置
            dp[0]=i*c1;//只能全部删除
            for(int j=1; j<=m; j++)
            {
                int tmp=dp[j];
                if(A[i-1]==B[j-1])
                    dp[j]=prev;
                else
                    dp[j]=min(prev+c2,min(dp[j]+c1,dp[j-1]+c0));
                prev=tmp;
            }
        }
        return dp[m];
    }
};