NC35：最小编辑代价

解法1：暴力递归

对于给定的单词 A 和 B，从左向右逐个匹配：
①对于 A 中当前遍历到的字符 A[i]，如果和 B[j] 相同，则不需要任何操作，继续向右遍历 i+1, j+1
②如果 A[i] != B[j]，则可以删除 A[i]，或者替换 A[i]，或者插入和 B[j] 相同的字符，因此存在三种选项
所以每次遍历匹配时，都存在 4 种可能的逻辑分支，设函数为dfs

• A[i] == B[j]
  dfs(str1,i+1,str2,j+1,ic,dc,rc)，i+1和j+1继续比较
• A[i] != B[j]

1. dfs(str1,i,str2,j+1,ic,dc,rc)+ic 说明str1中在i前插入一个元素，i和j+1继续比较

2. dfs(str1,i+1,str2,j+1,ic,dc,rc)+rc说明str1中i处元素被替换，i+1和j+1继续比较

3. dfs(str1,i+1,str2,j,ic,dc,rc)+dc说明str1中i处元素被删除，i+1和j继续比较

   //复杂度比较大，运行超时
    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));
    }

   解法1:动态规划

• dp[i][j]表示word1的前i个字符编辑成word2的前j个字符需要的最小操作数
• 初始状态：dp[i][0] = i，i次删除；dp[0][i] = i，i次插入
• 状态转移方程：

1. 当i字符等于j字符时：dp[i][j] = dp[i-1][j-1]，不需要额外操作
2. 当i字符不等于j字符时：dp[i][j] = Math.min(insert, delete, replace)
   ①int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j
   ②int delete = dp[i-1][j] + 1; i-1个编辑成j个字母，再删除一个i
   ③int replace = dp[i-1][j-1] + 1; i-1个编辑成j-1个字母，再将i替换成j

   public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++) {
            dp[i][0] = i*dc;
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j*ic;
        }
        for(int i = 1; i <= m; i++) {
            char c1 = str1.charAt(i-1);
            for(int j = 1; j <= n; j++) {
                char c2 = str2.charAt(j-1);
                if(c1 == c2) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    int insert = dp[i][j-1] + ic;
                    int delete = dp[i-1][j] + dc;
                    int replace = dp[i-1][j-1] + rc;
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        return dp[m][n];
    }