题解 | #最小编辑代价#

一.题目描述
NC35最小编辑代价
题目链接：https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4tpId=196&&tqId=37134&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给定两个字符串str1和str2，再给定三个整数ic，dc，rc，分别代表插入、删除、替换一个字符的代价，返回将str1编辑成str2的最小代价。
举例：
str1="abc" str2="adc" ic=5 dc=3 rc=2，从"abc"编辑到"adc"把b替换成d代价最小，为2；
str1="abc" str2="adc" ic=5 dc=3 rc=10，从"abc"编辑到"adc"，先删除b再插入d代价最小，为8；
二.算法(暴力搜索)
对于给出的两个字符串a和b,从左向右逐个匹配：
(1)对于a中当前遍历到的字符a[i]，如果b[j]相同，则不需要任何操作，继续向右遍历i+1，j+1
(2)如果a[i]!=b[i],可以删除a[i],或者替换a[i]，或者插入和b[j]相同的字符，因此存在三种选项所以每次遍历匹配的时候，都存在四种情况
当a[i]==b[j]: $dfs(a,i+1,b,j+1,ic,dc,rc)$ i+1和j+1继续比较
当a[i]!=b[j] :
1. $dfs(a,i,b,j+1,ic,dc,rc)+ic$ 说明a中在i前插入一个元素，i和j+1继续比较
2. $dfs(a,i+1,b,j+1,ic,dc,rc)+rc$ 说明a中i处元素被替换，i+1和j+1继续比较
3. $dfs(a,i+1,b,j,ic,dc,rc)+dc$ 说明a中i处元素被删除，i+1和j继续比较

/*java代码
开始用暴力搜索去尝试
但是很显然是超时的 读者可以看看 这个暴力搜索
*/
import java.util.*;
public class Solution {
    //复杂度比较大，运行超时
 public static int minEditCost (String str1, String str2, int ic, int dc, int rc) {
     return dfs(str1,0,str2,0,ic,dc,rc);
 }

 public static int dfs (String str1, int i, String str2, int j,int ic, int dc, int rc) {
     if(i==str1.length()){
         return (str2.length()-j)*ic;
     }
     if(j==str2.length()){
         return (str1.length()-i)*dc;
     }
     if(str1.charAt(i)==str2.charAt(j)){
         return dfs(str1,i+1,str2,j+1,ic,dc,rc);
     }
     return Math.min(dfs(str1,i,str2,j+1,ic,dc,rc)+ic,
                     Math.min(dfs(str1,i+1,str2,j+1,ic,dc,rc)+rc,
                             dfs(str1,i+1,str2,j,ic,dc,rc)+dc));
 }
}

时间复杂度： $O(2^{n})$
空间复杂度： $O(n^{2})$
优缺点：时间复杂度很大，但是容易想到
三.算法(动态规划)
图片说明
(1)动态规划： $dp[i][j]$ 表示str1的前i个字符编辑成str2的前j个字符需要的最小操作数
(2)边界处理：从表格可以看出来：
1.求第一行dp[0][j]， $dp[0][j]=ic*j$ ;
2.求第一列dp[i][0]， $dp[i][0]=dc*i$ ;
(3)状态转移：
1.当i字符等于j字符的时候： $dp[i][j]=dp[i-1][j-1]$ 相等不需要操作
2.当i字符不等于j字符的时候： $dp[i][j]$ 的值等于插入、替换和删除的最大值
插入： $dp[i][j-1]+ic$ ; 将 $i$ 个字符串转变为前 $j-1$ 个字符串在插入第j个字符
删除： $dp[i-1][j]+id$ ; 将 $i-1$ 个字符串转换为前 $j$ 个字符串删除第i个字符
替换： $dp[i-1][j-1]+rc$ ; $i-1$ 个编辑成 $j-1$ 个字母，再将i替换成j

class Solution {
public:
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int m = str1.size();
        int n = str2.size();
        int dp[5005][5005];
//刚开始对边界的初始化
        for(int i=0;i<=m;i++) dp[i][0]=i*dc;
        for(int j=0;j<=n;j++) dp[0][j]=j*ic;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                int a=dp[i][j-1]+ic;//插入
                int b=dp[i-1][j]+dc;//删除
                int c=dp[i-1][j-1];//替换
                if(str1[i-1]!=str2[j-1]) c+=rc;
                dp[i][j]=min(a, min(b, c));
            }
        }
        return dp[m][n];
    }
};

时间复杂度： $O(n^{2})$
空间复杂度： $O(n^{2})$ 需要额外开辟二维数组
优缺点：效率高，但是状态转移方程比较难想