力扣 241. 为运算表达式设计优先级

题目来源：https://leetcode.cn/problems/different-ways-to-add-parentheses/

大致题意：
给一个表达式字符串 s，可以在表达式中任意添加有效的小括号改变表达式的运算优先级，输出所有可能的结果，可以包含重复结果

思路

设有表达式 a 和 b，操作符 op，那么 a op b 的结果为表达式 a 的所有结果 与 表达式 b 所有结果进行 op 运算的值的集合（不去重）

于是可以使用 dp[i][j] 表示 s[i, j] 表达式的所有结果，那么 dp[0][n - 1] 即为 s 的所有结果

• 对于 dp[i][j] 代表的表达式 s[i, j] 来说，若其中有操作符索引为 k，操作符类型为 op，那么 dp[i][j] 即为 dp[i][k - 1] 的所有值与 dp[k + 1][j] 的所有值进行 op 运算

为了方便运算，可以先将原表达式处理成 ops 数组，数组中的每个元素为操作数或操作符，操作符使用数字代替（-1 = ‘+’， -2 = ‘-’， -3=‘×’）

然后在进行 dfs，并通过 dp[i][j] 数组实现记忆化搜索

DFS + 记忆化搜索

1. 将表达式处理成操作数数组 ops
2. 进行 DFS 搜索，对于当前搜索范围 [l, r] 中的每个操作符，设操作符索引为 k，搜索 [l, k - 1] 的所有结果和 [k + 1, r] 的所有结果；特别地，若 l == r，则当前表达式的结果即为 ops[l] 代表的值；搜索时，若 dp[i][j] 已有结果，表示已经搜索过，无需重复搜索

代码：

public List<Integer> diffWaysToCompute_DFS(String expression) {
        // 操作数数组
        List<Integer> ops = new ArrayList<>();
        int n = expression.length();
        // 将表达式处理为操作数数组
        for (int i = 0; i < n; ) {
            char ch = expression.charAt(i);
            // 若当前字符不是数字，则为操作符，将操作符处理为数字存入
            if (!Character.isDigit(ch)) {
                switch (ch) {
                    case '+':
                        ops.add(-1);
                        break;
                    case '-':
                        ops.add(-2);
                        break;
                    default:
                        ops.add(-3);
                }
                // 更新索引
                i++;
            } else {
                // 否则，当前字符为数字，取出该数放入数组
                int num = 0;
                while (i < n && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + expression.charAt(i) - '0';
                    i++;    // 更新索引
                }
                ops.add(num);
            }
        }
        int size = ops.size();
        // 记忆搜索结果
        List<Integer>[][] dp = new List[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                dp[i][j] = new ArrayList<>();
            }
        }
        // dfs
        return dfs(dp, 0, size - 1, ops);
    }

    /**
     * dfs 搜索表达式 ops[l, r] 的所有结果
     * 
     * @param dp    记忆搜索结果的集合
     * @param l     左边界
     * @param r     右边界
     * @param ops   操作数数组
     * @return
     */
    public List<Integer> dfs(List<Integer>[][] dp, int l, int r, List<Integer> ops) {
        // 若当前表达式已经搜索过，无需重复搜索
        if (dp[l][r].isEmpty()) {
            // 若表达式长度为 1，直接添加该操作数
            if (l == r) {
                dp[l][r].add(ops.get(l));
            } else {
                // 遍历表达式所有操作符
                for (int i = l; i < r; i += 2) {
                    // 左侧运算结果
                    List<Integer> left = dfs(dp, l, i, ops);
                    // 右侧运算结果
                    List<Integer> right = dfs(dp, i + 2, r, ops);
                    // 两侧进行 op 运算
                    for (int leftNum : left) {
                        for (int rightNum : right) {
                            switch (ops.get(i + 1)) {
                                case -1:
                                    dp[l][r].add(leftNum + rightNum);
                                    break;
                                case -2:
                                    dp[l][r].add(leftNum - rightNum);
                                    break;
                                case -3:
                                    dp[l][r].add(leftNum * rightNum);
                                    break;
                            }
                        }
                    }
                }
            }
        }
        return dp[l][r];
    }
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
77
78
79
80
81
82
83
84
85
86