[数据结构与算法]化繁为简的分治法：——（LC241（我太菜了做得头疼））

题目：

给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果

输入是一个字符串，表示数学表达式；输出是一个数组，存储所有不同的加括号结果。

题解：

顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子
问题，再将子问题进行处理合并，从而实现对原问题的求解。

例如：在排序章节展示的归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为 1 的子数组开始，最终合成一个大数组。

自上而下的分治可以和 memoization 结合，避免重复遍历相同的子问题。如果方便推
导，也可以换用自下而上的动态规划方法求解。

利用分治思想，我们可以把加括号转化为，对于每个运算符号，先执行处理两侧的数学表达
式，再处理此运算符号

最巧妙的地方就是做一个预处理，把每个数字提前转为 int 然后存起来，同时把运算符也都存起来。这样的话我们就有了两个 list，一个保存了所有数字，一个保存了所有运算符。

2 * 3 - 4 * 5

存起来的数字是 numList = [2 3 4 5]，

存起来的运算符是 opList = [*, -, *]。

dp[i][j]?也比较好定义了，含义是第?i?到第?j?个数字（从?0?开始计数）范围内的表达式的所有解。

举个例子，2 * 3 - 4 * 5 dp[1][3] 就代表第一个数字 3 到第三个数字 5 范围内的表达式 3 - 4 * 5 的所有解。

初始条件的话，也很简单了，就是范围内只有一个数字。

2 * 3 - 4 * 5

dp[0][0] = [2]，dp[1][1] = [3]，dp[2][2] = [4]，dp[3][3] = [5]。

?

有了一个数字的所有解，然后两个数字的所有解就可以求出来。

有了两个数字的所有解，然后三个数字的所有解就和解法一求法一样。

把三个数字分成两部分，将两部分的解两两组合起来即可。

两部分之间的运算符的话，因为表达式是一个数字一个运算符，所以运算符的下标就是左部分最后一个数字的下标。
看下边的例子。

2 * 3 - 4 * 5
存起来的数字是 numList = [2 3 4 5]，
存起来的运算符是 opList = [*, -, *]。

假设我们求 dp[1][3]
也就是计算 3 - 4 * 5 的解
分成 3 和 4 * 5 两部分，3 对应的下标是 1 ，对应的运算符就是 opList[1] = '-' 。
也就是计算 3 - 20 = -17
? ??
分成 3 - 4 和 5 两部分，4 的下标是 2 ，对应的运算符就是 opList[2] = '*'。
也就是计算 -1 * 5 = -5
? ??
所以 dp[1][3] = [-17 -5]

四个、五个... 都可以分成两部分，然后通过之前的解求出来。

直到包含了所有数字的解求出来，假设数字总个数是?n，dp[0][n-1]?就是最后返回的了。

class Solution {
 public List<Integer> diffWaysToCompute(String input) {
    List<Integer> numList = new ArrayList<>();
    List<Character> opList = new ArrayList<>();
    char[] array = input.toCharArray();
    int num = 0;
    for (int i = 0; i < array.length; i++) {
        if (isOperation(array[i])) {
            numList.add(num);
            num = 0;
            opList.add(array[i]);
            continue;
        }
        num = num * 10 + array[i] - '0';
    }
    numList.add(num);
    int N = numList.size(); // 数字的个数

    // 一个数字
    ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];
    for (int i = 0; i < N; i++) {
        ArrayList<Integer> result = new ArrayList<>();
        result.add(numList.get(i));
        dp[i][i] = result;
    }
    // 2 个数字到 N 个数字
    for (int n = 2; n <= N; n++) {
        // 开始下标
        for (int i = 0; i < N; i++) {
            // 结束下标
            int j = i + n - 1;
            if (j >= N) {
                break;
            }
            ArrayList<Integer> result = new ArrayList<>();
            // 分成 i ~ s 和 s+1 ~ j 两部分
            for (int s = i; s < j; s++) {
                ArrayList<Integer> result1 = dp[i][s];
                ArrayList<Integer> result2 = dp[s + 1][j];
                for (int x = 0; x < result1.size(); x++) {
                    for (int y = 0; y < result2.size(); y++) {
                        // 第 s 个数字下标对应是第 s 个运算符
                        char op = opList.get(s);
                        result.add(caculate(result1.get(x), op, result2.get(y)));
                    }
                }
            }
            dp[i][j] = result;

        }
    }
    return dp[0][N-1];
}

private int caculate(int num1, char c, int num2) {
    switch (c) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
    }
    return -1;
}

private boolean isOperation(char c) {
    return c == '+' || c == '-' || c == '*';
}


}

总结记录来源：力扣（LeetCode）（一位大神的题解）