【算法】【递归与动态规划模块】逻辑表达式组成期望结果的所有种数计算

前言

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

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

问题介绍

原问题
给定str，str为一个逻辑表达式，如 1^0|0|1,给定一个target 为true或者false，求整个表达式结果为target的所有组合方式种数
如:
给定target = false
组合有：
1^((0|0)|1)
1^(0|(0|1))
两种，因此结果返回为2

解决方案

原问题：
递归方案：
1、首先入参有arr(char数组). left（arr的左边界），right（arr的右边界），aim（数组组合需要达到的目标），函数原型：fun（arr, left, right, aim），返回值为组成的结果种数
2、状态之间的递推关系：每一个状态都循环数组，仅判断数组中的运算符部分，有如下判断逻辑：
aim为true：
如果为 ‘&’：两边都必须为1，结果返回种数，相乘，即 fun(arr, left, i-1, true) * fun(arr, i+1, right, false)
如果为 ‘|’：两边有一边为1即可
如果为‘^’: 两边不一样即可
aim为false：
如果为‘&’：两边有一个为1即可
如果为‘|’ ：两边都为false才行
如果为‘^’ : 两边一样即可

只要满足即可将种数累加最终返回结果即可

动态规划方案：
1、申请内存将动态规划中的状态结果进行存储，首先变量为left，right，aim，因此应该申请一个三维的dp，由于aim只有两个状态，因此三维的大小为legthlength2,也可以拆成两个一维的矩阵比较好理解一些.所以最终产生两个矩阵 trueDp，falseDp
2、对于trueDp来讲，首先left不会大于right，因此只实现一半矩阵即可，falseDp同理，初始化时初始化斜对角，因为只有一个元素时，达到目标的种数可以直接计算出来。
3、递推关系：计算trueDp[i][j]时，即计算arr[i…j]目标为true的所有种数，因此需要循环 arr[i…j]，计算每一个符号，逻辑和递归方案中的逻辑相同，从左到右循环发现需要依赖trueDp[i][i+2…j-2],falseDp[i][i+2…j-2], trueDp[i+2…j-2][j],falseDp[i+2…j-2][j],即前面的和下面的，所以dp填充顺序应该是从左到右，从下到上。

代码编写

java语言版本

原问题：
经典递归版本：

   /**
     * 二轮测试：暴力递归
     * @param str
     * @return
     */
    public static int getNumCp1(String str, boolean aim) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        if (!isValid(chars)) {
            return 0;
        }
        return processForCp1(chars, 0, chars.length-1, aim ? '1' : '0');
    }

    /**
     * 递归主体
     * @param chars
     * @param start
     * @param end
     * @return
     */
    private static int processForCp1(char[] chars, int start, int end, char aim) {
        if (start > end) {
            System.out.println(start + ", " + end);
        }
        if (start == end) {
            // 只有一个元素
            return chars[start] == aim ? 1 : 0;
        }
        int res = 0;
        for (int i = start + 1; i <= end-1; i +=2) {
            // aim影响了符号两边的判断
            if (aim == '1') {
                // 目标是true
                if (chars[i] == '&') {
                    // 两边必须是1
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '1');
                }else if (chars[i] == '|') {
                    // 有一边是1即可
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '1');
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '0');
                    res += processForCp1(chars, start, i-1, '0') * processForCp1(chars, i+1, end, '1');
                }else if (chars[i] == '^') {
                    // 两边不一样就行
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '0');
                    res += processForCp1(chars, start, i-1, '0') * processForCp1(chars, i+1, end, '1');
                }
            }else {
                // 目标是false
                if (chars[i] == '&') {
                    // 两边不一样即可
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '0');
                    res += processForCp1(chars, start, i-1, '0') * processForCp1(chars, i+1, end, '1');
                }else if (chars[i] == '|') {
                    // 都是0才行
                    res += processForCp1(chars, start, i-1, '0') * processForCp1(chars, i+1, end, '0');
                }else if (chars[i] == '^') {
                    // 两边一样
                    res += processForCp1(chars, start, i-1, '1') * processForCp1(chars, i+1, end, '1');
                    res += processForCp1(chars, start, i-1, '0') * processForCp1(chars, i+1, end, '0');
                }
            }
        }
        return res;
    }
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

经典动态规划版本：

    /**
     * 动态规划方法
     * @param str
     * @param aim
     * @return
     */
    public static int dpCp1(String str, boolean aim) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char aimC = aim ? '1' : '0';
        char[] chars = str.toCharArray();
        if (!isValid(chars)) {
            return 0;
        }
        // 创建两张表，一张为结果为true种数表，另一个是结果为false种数表
        int[][] trueDp = new int[chars.length][chars.length];
        int[][] falseDp = new int[chars.length][chars.length];
        // 填空斜对角
        for (int i = 0; i < chars.length; i+=2) {
            trueDp[i][i] = chars[i] == '1' ? 1 : 0;
            falseDp[i][i] = chars[i] == '0' ? 1 : 0;
        }
        for (int j = 2; j < chars.length; j+=2) {
            for (int i = j-2; i >= 0; i-=2) {
                trueDp[i][j] = 0;
                falseDp[i][j] = 0;
                for (int k = i+1; k <= j-1; k +=2) {
                    // k代表当前范围内的符号索引
                    if (chars[k] == '&') {
                        trueDp[i][j] += trueDp[i][k-1] * trueDp[k+1][j];

                        falseDp[i][j] += falseDp[i][k-1] * trueDp[k+1][j];
                        falseDp[i][j] += trueDp[i][k-1] * falseDp[k+1][j];
                    }else if (chars[k] == '|') {
                        trueDp[i][j] += falseDp[i][k-1] * trueDp[k+1][j];
                        trueDp[i][j] += trueDp[i][k-1] * falseDp[k+1][j];

                        falseDp[i][j] += falseDp[i][k-1] * falseDp[k+1][j];
                    }else if (chars[k] == '^') {
                        trueDp[i][j] += falseDp[i][k-1] * trueDp[k+1][j];
                        trueDp[i][j] += trueDp[i][k-1] * falseDp[k+1][j];

                        falseDp[i][j] += falseDp[i][k-1] * falseDp[k+1][j];
                        falseDp[i][j] += trueDp[i][k-1] * trueDp[k+1][j];
                    }
                }
            }
        }
        // 这里好理解些就不写节省空间的版本了，dp可以减小一半
        if (aimC == '1') {
            return trueDp[0][chars.length-1];
        }else {
            return falseDp[0][chars.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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题跟之前遇到的所有动态规划解决思路都不太一样，所以这里我觉得可以将其归为一种递归动态规划的类型，后面还有一道相似的场景需要用到这种思路。
首先我们都用最基本的视角来对待这道题，我刚开始想到的就是暴力递归arr，循环遍历所有组合，即[i…i+1][i…i+2] … [i+1… i+2] … [j-1…j]
arr剩下的部分作为整体继续递归，这样的话一共分为三个部分 [left…i-k][i-k+1…i…i+k-1][i+k…right]，三个数组，数组的连接处为符号，那么得到目标的所有种数计算起来就非常的麻烦，因为需要三个部分进行可能性分析。。。所以书中的优化就是将整个数组分为数字和符号，仅遍历符号，将数组分为两个部分，两边之间进行可能性分析，最终获得正确答案。
在书中思路我们发现，一个状态的计算需要循环数组计算所有可能性这种，当遇到这种需要循环计算当前状态值的问题时，可以分析符合目标的可能性，然后将子递归作为整体列出递推表达式,具体一点就是，循环计算每一个符号时，需要分析两边有几种可能性可以符合目标，将可能性全部列出来，比如&目标为true的可能性只有一种就是左右都是true，因此结果就是 左边目标为true的种数*右边目标为true的种数，左右边分别是当前状态的子递归。

动态规划的方式由递归方式演变而来，如果知道递归方式，动态规划方式非常的简单。

写在最后

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