NC35 题解 | #最小编辑代价#

题目大意

• 给你两个字符串，需要你通过执行三种操作，将一个字符串修改为另一个字符串。但是你执行这三种操作都是有代价的。三种操作分别对应三种代价。你需要使用最少的代价将这个字符串修改为另一个字符串。

思路分析

• 首先，这个题目是比较难的，我来大致介绍一下我的思路和想法。对于这个问题，最开始我想的是利用DP进行求解。但是，我定义的dp方程是dp[5010][3]，也就是分别对应每个位置执行三种操作的最小的代价。但是这里我进行推导的时候发现这个是有问题的。在这个状态的定义中，我们无法进行状态的转移。而且这样定义的dp是没有后效性的。所以，我们需要想其他办法。

• 然后，我发现，其实这个可以和最长公共子序列的题目相联系（LCS）,我们定义dp[i][j]分别表示字符串str1的前i个字符和字符串str2的前j个字符完全匹配之后的最小的代价。然后，我们来看一下这个是否有合法的状态转移。当我们的状态到达i,j的时候，我们确保了(i-1,j),(i,j-1)和(i-1,j-1)这些都是已经知道了的。那么根据题目意思，我们想要把第一个字符串转换为另一个字符串。我们需要执行三种操作，当然，我们并不知道执行哪种操作是最好的。于是我们枚举存储出三种操作的情况，假设在str1这个位置执行删除操作。那么为了保持str1[0...i]和str2[0...j]完全匹配的话，就可以由str1[0...i-1]和str2[0...j]完全匹配的情况转移过来。也就是,同理，假如执行插入操作，那么为了保持str1[0...i]和str2[0...j]完全匹配的话，就可以由str1[0...i]和str2[0...j-1]完全匹配的情况转移过来。也就是;执行替换操作同理可以得到。这三者取最小的即可。所以，这种状态方程的定义是存在后效性的。接下来，我们就可以码代码了。但是在码代码之前我们需要初始化一些条件，为了实现状态的顺利转移，我们肯定要定义状态的起点，这里状态的起点就是当两个字符串其中一个长度是0的时候，我们先进行预处理。然后就可以顺利地转移啦！

• 请结合下图进行理解

解法一 普通DP

• 这种方法地思路如上，但是其实还可以优化地，具体请看下一种解法。

• 代码如下

  • 我们需要循环枚举两个字符串当前地位置来表示当前地状态，所以时间复杂度为O(nm)
  • 开了一个二维数组存储每个状态，空间复杂度为O(nm)

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整型
     */
    // dp[i][j]表示的是str1的前i个字符和str2的前j个字符完全匹配的所需要的最小的花费
    int dp[5010][5010];
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        int n=str1.size();
        int m=str2.size();
        for(int i=1;i<=n;i++){
            dp[i][0]=i*dc;
        }
        for(int i=1;i<=m;i++){
            dp[0][i]=i*ic;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(str1[i-1]==str2[j-1]){
                    // 此时匹配了，那么不进行操作
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    // 此时字符不匹配，执行三种操作中最优的那种
                    int ins=dp[i][j-1]+ic;
                     // 在这个位置插入一个字符，使得[0,i]和[0,j-1]合法的情况下，str1[i+1]==str2[j]
                    int del=dp[i-1][j]+dc;
                    // 在这个位置删除一个字符，使得[0,i-1]字符和[0,j]字符合法
                    int rep=dp[i-1][j-1]+rc;
                    // 替换掉这个字符，就是从[0,i-1]和[0,j-1]进行转移 
                    dp[i][j]=min(ins,min(del,rep));  // 取最小的
                }
            }
        }
        return dp[n][m];
    }
};

解法二 DP空间优化

• 在上面那种解法我们可以看到，对于状态方程地转移虽然没有问题，但是我们的数组开了一个二维的很大的。但是在进行状态的转移的时候，我们可以发现，其实只用了这个状态的上一个状态。而没有用之前更早的状态。学过DP算法的一般都知道，这种情况下一般是可以利用滚动数组优化掉一维空间的。那么我们就可以看看怎么优化这一维呢？首先，我们可以确实我们可以优化的是外面那一维状态。这个可以根据第一种解法的状态转移方程得出，我们重新定义状态方程dp[i]表示的是在当前的str1的情况下，字符串str2的前i个字符需要和str1进行匹配的最小的代价。同样，对于之前的哪三种情况也是同样的进行转移。但是这里要注意的是我们我们为了用到上一个状态，我们需要使用一个pre变量临时存储每个状态的上一个状态的最小代价。具体请看代码实现。

• 代码如下
  • 还是需要遍历字符串的所有位置进行状态转移，时间复杂度为O(nm)
  • 这种方法优化了一维，只记录了str2的状态，空间复杂度为O(n)。

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 dp[5010];  // dp[i]表示对于此时的str1，需要满足和str2的前i个字符相等的最小代价
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        int n=str1.size(),m=str2.size();
        for(int i=0;i<=m;i++){
            // 此时str1的长度为0的情况下，我们需要求出str1和str2的前i个字符匹配的最小代价
            dp[i]=i*ic;
        }
        for(int i=1;i<=n;i++){
            int pre=dp[0]; // 提前记录此时str2的前0个字符需要匹配的最小代价，pre用来存储前一个状态的最小代价
            dp[0]=i*dc;
            for(int j=1;j<=m;j++){
                // 此时在str1字符串长度为i的情况下，str2的前j个字符要完全匹配的最小的代价
                int ins=dp[j-1]+ic;
                int del=dp[j]+dc;
                int rep=pre+(str1[i-1]==str2[j-1]?0:rc);
                pre=dp[j]; // 及时更新，给下一个状态使用
                dp[j]=min(ins,min(del,rep));
            }
        }
        return dp[m];
    }
};