C++ 解法, 执行用时: 1ms, 内存消耗: 496KB, 提交时间: 2017-09-02

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) 
    {
        // write code here
        /*
            当A=="" 或者B==""时，cost是删除或插入的代价
            当A!="" 且 B!= ""时
            A[i] == B[j] D[i][j] = D[i-1][j-1]
            A[i] != B[j] D[i][j] = MIN{D[i-1][j-1]+c2(修改一个值)，D[i-1][j]+c1(删除一个值)，D[i][j-1]+c0(插入一个值)}
            长度为i的A修改为长度为j的B可以分为：
			1、长度为i的A修改为长度为j-1的B，然后插入j位置的字符；
			2、长度为i-1的A修改为长度为j的B，然后删除i位置的字符；
			3、长度为i-1的A修改为长度为j-1的B，然后i位置的字符修改为j位置的字符。
        */
        vector<vector<int> > D(n+1, vector<int>(m+1,0));
        for(int i = 1; i < n + 1;i ++)
        {
            D[i][0] = D[i-1][0] + c1;
        }
        for(int j = 1; j < m + 1 ; j ++)
        {
            D[0][j] = D[0][j-1] + c0;
        }
        for(int i = 1; i < n + 1; i ++)
        {
            for(int j = 1; j < m + 1 ; j ++)
            {
                if (A[i - 1] == B[j - 1])
                {
                    D[i][j] = D[i - 1][j - 1];
                }
                else
                {
                    D[i][j] = min(D[i - 1][j - 1] + c2, min(D[i][j - 1] + c0, D[i - 1][j] + c1) );
                }
            }
        }
        return D[n][m];        
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 476KB, 提交时间: 2020-10-31

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        int i,j,res;
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        for(i=0;i<=n;i++)
            dp[i][0]=c1*i;
        for(i=0;i<=m;i++)
            dp[0][i]=c0*i;
        int r1,r2,r3,r;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(A[i-1]==B[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else
                {
                    r1=dp[i][j-1]+c0;
                    r2=dp[i-1][j]+c1;
                    r3=dp[i-1][j-1]+c2;
                    r=r1<r2?r1:r2;
                    r=r<r3?r:r3;
                    dp[i][j]=r;
                }
            }
        }
        res=dp[n][m];
        return res;
    }
};