Red: https://pdai.tech/md/algorithm/alg-core-divide-and-conquer.html

    分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。@pdai

    题目
    （1）给表达式加括号：

    1. Input: "2-1-1".
    3. ((2-1)-1) = 0
    4. (2-(1-1)) = 2
    6. Output : [0, 2]

    Ans：

    1. public List<Integer> diffWaysToCompute(String input) {
    2.     List<Integer> ways = new ArrayList<>();
    3.     for (int i = 0; i < input.length(); i++) {
    4.         char c = input.charAt(i);
    5.         if (c == '+' || c == '-' || c == '*') {
    6.             List<Integer> left = diffWaysToCompute(input.substring(0, i));
    7.             List<Integer> right = diffWaysToCompute(input.substring(i + 1));
    8.             for (int l : left) {
    9.                 for (int r : right) {
    10.                     switch (c) {
    11.                         case '+':
    12.                             ways.add(l + r);
    13.                             break;
    14.                         case '-':
    15.                             ways.add(l - r);
    16.                             break;
    17.                         case '*':
    18.                             ways.add(l * r);
    19.                             break;
    20.                     }
    21.                 }
    22.             }
    23.         }
    24.     }
    25.     if (ways.size() == 0) {
    26.         ways.add(Integer.valueOf(input));
    27.     }
    28.     return ways;
    29. }