【算法】【递归与动态规划模块】字符串之间转换的最小代价

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定str1和str2，现在str1需要通过 新增、删除或替换 来转成str2，给定新增、删除、替换的代价分别是 ins，del，up，求str1转成str2的最小代价是多少？

如：
str1 = “abc”;
str2 = “adc”;
ins = 5;
del = 3;
up = 2;
从str1转成str2最小的代价就是替换第二个字符，代价为2
如果：
ins = 5;
del = 3;
up = 100;
str1转成str2最小的代价就是删除第二个字符，插入字符d即可。代价为8；

解决方案

原问题：
动态规划两个要素：
1、dp[i][j]代表str1[0…i] 转成str2[0…j] 需要的最小代价
2、递推关系， dp[i][j] = Min(dp[i-1][j] + del , dp[i][j-1] + ins, char[i] == char[j] ? dp[i-1][j-1] : dp[i-1][-1] + up);

代码编写

java语言版本

原问题：
动态规划：

    /**
     * 经典动态规划方法
     * 计算str1到str2的最小代价
     * @param str1 字符串1
     * @param str2 字符串2
     * @param ins 插入操作的代价
     * @param del 删除操作的代价
     * @param up 更新操作的代价
     * @return
     */
    public static int minEditCP1(String str1, String str2, int ins, int del, int up) {
        if (str1 == null || str2 == null
                || str1.length() == 0 || str2.length() == 0) {
            return 0;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] dp = new int[chars1.length][chars2.length];
        // 如果相等，代价为0，如果不相等，一种是替换，一种是先删除后增加
        dp[0][0] = chars1[0] == chars2[0] ? 0 : Math.min(up, ins+del);
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][0] + del;
        }
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = dp[0][j-1] + ins;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <  dp[0].length; j++) {
                // 不相等的时候，可以替换、先删除后增加，单增加
                // 替换情况,相等的时候不用替换
                int upMin = dp[i-1][j-1] + (chars1[i] == chars2[j] ? 0 : up);
                // 先删除后增加
                int delMin = dp[i-1][j] + del;
                int insMin = dp[i][j-1] + ins;
                dp[i][j] = Math.min(upMin, Math.min(delMin, insMin));

            }
        }
        return dp[chars1.length-1][chars2.length-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

动态规划降低内存版本：

    public static int minEditCPReduceMem(String str1, String str2, int ins, int del, int up) {
        if (str1 == null || str2 == null
                || str1.length() == 0 || str2.length() == 0) {
            return 0;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[] dp = new int[chars2.length];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i-1] + ins;
        }
        for (int i = 1; i < chars1.length; i++) {
            int tem = dp[0];
            dp[0] += del;
            for (int j = 1; j < dp.length; j++) {
                int upMin = tem + (chars1[i] == chars2[j] ? 0 : up);
                int insMin = dp[j-1] + ins;
                int delMin = dp[j] + del;
                // 更新前将老值给tem
                tem = dp[j];
                dp[j] = Math.min(upMin, Math.min(delMin, insMin));
            }
        }
        return dp[chars2.length-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题第一次做的时候看书上的解释有点不太懂，这次自己想出来的理解方式可能会更有意思一点，这里分享给大家，首先dp[i][j]代表str1[0…i] 转到str2[0…j]所需要的最小代价，也就是我们当前要求的值，那么已知dp[i-1][j]和dp[i-1][j-1] 还有dp[i][j-1] 的值，下面一一解释他们的含义：
dp[i-1][j] 表示str[0…i-1]这几个元素转str2[0…j]所需要的最小代价，这里不带str1[i],那么str1[0…i-1]转成了str2[0…j]就已经达到目的了，str[i]就是个多余的，那么这个时候需要一次del操作吧str[i]删掉，所以第一种方式的代价 dp[i-1][j] + del
dp[i][j-1] 表示str[0…i]这几个元素转str2[0…j-1]所需要的最小代价，这里是带上str1[i]以后还是只转成了str2[0…j-1],少个str2[j]，所以这里需要加一个str2[j]那么第二种方式的代价就是dp[i][j-1] + ins;
dp[i-1][j-1] 表示str1[0…i-1] 直接实现str2[0…j-1]，此时str1还剩个str1[i]没有转 ，str2还剩下str2[j] 没有转，如果两个元素相等，那么直接就不需要任何操作了，如果不相等，那么需要一次替换操作，所以第三种方法就是 dp[i-1][j-1] : dp[i-1][-1] + up

三种方法中代价最小的那个就是dp[i][j]了。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！