【算法】【递归与动态规划模块】两个字符串的公共最长子序列

前言

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

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

问题介绍

原问题
给定两个字符串str1和str2，求两个字符串的最长公共子序列
如：
str1:1A2C3D4B56
str2：B1D23CA45B6A
结果为：
12C4B6 或 123456

解决方案

原问题：
动态规划方法：
1、构造动态规划矩阵，dp[i][j] 代表str1[0…i]和str2[0…j]之间的最长公共子序列的长度
2、递归关系：
· 比较dp[i-1][j]和dp[i][j-1]的值，如果不相同，则找大的赋值给dp[i][j]，如果相同，则比较str1[i]和str2[j]是否相同，如果相同则dp[i][j] = dp[i-1][j] + 1;

代码编写

java语言版本

原问题：
动态规划方法：

    /**
     * 获取dp矩阵
     * @return
     */
    public static int[][] getDpCP(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] dp = new int[chars1.length][chars2.length];
        dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
        // 初始化
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][0] == 1 || chars2[0] == chars1[i] ? 1 : 0;
        }
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i] = dp[0][i-1] == 1 || chars1[0] == chars2[i] ? 1 : 0;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (dp[i-1][j] == dp[i][j-1]) {
                    dp[i][j] = chars1[i] == chars2[j] ? dp[i-1][j] + 1 : dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp;
    }


    /**
     * 根据dp获取序列
     * @param str1
     * @param str2
     * @return
     */
    public static String getSeqCP(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] dpCP = getDpCP(str1, str2);
        int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
        char[] charRes = new char[maxLen];
        int index = 0;
        int i = dpCP.length-1;
        int j = dpCP[0].length-1;
        while (i != 0 && j != 0) {
            if (dpCP[i-1][j] == dpCP[i][j-1] && dpCP[i-1][j] == dpCP[i][j] - 1) {
                // 添加当前值
                charRes[index++] = chars1[i];
                i--;
            }else if (dpCP[i-1][j] >= dpCP[i][j-1]){
                i--;
            }else {
                j--;
            }
        }
        if (dpCP[i][j] == 1) {
            charRes[index++] = i == 0 ? chars1[i] : chars2[j];
        }
        // 翻转
        CommonUtils.reverseChar(charRes, 0, index);
        return String.valueOf(charRes, 0, index);
    }


    public static void main(String[] args) {
        System.out.println(getSeqCP("1A2C3D4B56", "B1D23CA45B6A"));
    }

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

首先dp[i][j]的含义是非常容易想到的吧，就算是递归方法，无非入参就是str1和str2，i，j，四个变量，这里没有使用暴力递归了，因为实在是太消耗没用的资源了，所以我们把它淘汰了！
第二个要素就是递推公式的由来，这里我第二遍做这个题，时隔半年，最后还是想到了，首先dp[i-1][j]代表str1[0…i-1]和str2[0…j]之间的最长子序列长度，dp[i][j-1]就不用说了，那么如果两个值相等说明 有没有str1[i] ，str2[j]都无所谓，也间接说明那两个状态中的最长子序列不包含当前值，那么如果当前str1[i] = str2[j]刚好dp[i][j] 状态能够将最长子序列拓展一个值。 那么如果str1[i] ！= str2[j]不相等就仍然继承原来的两个状态。
dp[i-1][j] ！= dp[i][j-1] 的情况是什么呢？我这里认为，如果不相等说明这两个状态跟str1[i] 和str2[j] 有关系，去掉某个值的时候影响了最长子序列，那么这个时候不管str1[i] 与str2[j]是否相等，dp[i][j] 都只能继承到前面两个状态中较大的那个，这个要细品一下，才能理解。

最后说一下如何求子序列，当我们求得最长子序列长度dp之后，如果理解了dp矩阵的求解过程和原理之后，倒回来求序列就比较好理解了，
从dp最后一个状态开始，当前面的和上面的两个状态，也就是dp[i-1][j] 和 dp[i][j-1]相等的时候判断当前dp状态是否是前面两个状态+1，如果是的，那么说明当前值是 被选入最长子序列的，如果没有+1，说明当前值没有被选入，那么走较大的（相等时走哪个都可以），如果dp[i-1][j] 和 dp[i][j-1]不相等，那么走较大的，不选入任何子序列。
为什么结果中会有两种答案呢？
就是因为dp[i-1][j] 和 dp[i][j-1]相等的时候可以有两种选择，如果你选择了其中一种就会得到一种答案，另一种就会得到另一种答案。

写在最后

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