🚩传送门：https://leetcode-cn.com/problems/different-ways-to-add-parentheses/

题目

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: “2-1-1” 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2

示例 2:

输入: “23-45” 输出: [-34, -14, -10, -10, 10] 解释: 2 -2 -5 -17 10 -10 -10 -34 (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10

解题思路：分治

分治算法三步走：

  1. 分解：分成部分，分别求解
  2. 解决：实现一个递归函数，输入算式，返回算式解
  3. 合并：合并部分的解，得出最终解

本题解 采用了 分治 的思想：

  1. [分解]：遍历字符串，遇到操作符，就将左右两边的字符串，分别当作 两个表达式
  2. [解决]：带入算式，求解两侧的答案集合
  3. [合并]：将两侧的答案集合通过当前操作符组合成心的答案集合。

简洁的说明代码：

  1. class Solution:
  2.     def diffWaysToCompute(self, input: str) -> List[int]:
  3.         # 如果只有数字,直接返回
  4.         if input.isdigit():
  5.             return [int(input)]
  7.         res = []
  8.         # 依次遍历字符串,读取运算符
  9.         for i, char in enumerate(input):
  10.             if char in ['+', '-', '*']:
  11.                 # 1.分解:遇到运算符,计算左右两侧的结果集
  12.                 #     目的:解决diffWaysToCompute 递归函数求出子问题的解
  13.                 left = self.diffWaysToCompute(input[:i])        #left得到的是左侧结果集
  14.                 right = self.diffWaysToCompute(input[i+1:])        #right得到的是右侧结果集
  15.                 # 2.合并:根据运算符合并子问题的解
  16.                 for l in left:
  17.                     for r in right:
  18.                         if char == '+':
  19.                             res.append(l + r)
  20.                         elif char == '-':
  21.                             res.append(l - r)
  22.                         else:
  23.                             res.append(l * r)
  25.         return res

解题思路：动态规划

dp 数组的含义比较难定义，需要做一个预处理，把字符串中的每个数字和运算符分开存起来 。

这样的话我们就有了两个 list，一个保存了所有数字，一个保存了所有运算符。

举例子：2 3 - 4 5

存起来的数字是 numList = [2345] 存起来的运算符是 opList = [, -, ]

👉 定义 含义是第 到第 个数字（从 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]。

  1. package dp.dp241;
  3. import java.util.ArrayList;
  4. import java.util.List;
  6. public class demo {
  7.     public static List<Integer> diffWaysToCompute(String input) {
  8.         List<Integer> numList = new ArrayList<>();
  9.         List<Character> opList = new ArrayList<>();
  10.         char[] array = input.toCharArray();
  11.         int num = 0;
  12.         //=预处理部分=
  13.         for (int i = 0; i < array.length; i++) {
  14.             if (isOperation(array[i])) {
  15.                 //由于之前处理的整数并未存储，此处存储
  16.                 numList.add(num);
  17.                 num = 0;
  18.                 opList.add(array[i]);
  19.                 continue;
  20.             }
  21.             //整数处理
  22.             num = array[i] - '0';
  23.         }
  24.         numList.add(num);
  25.         int N = numList.size(); // 数字的个数
  27.         // 初始条件:一个数字
  28.         ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];
  29.         for (int i = 0; i < N; i++) {
  30.             ArrayList<Integer> result = new ArrayList<>();
  31.             result.add(numList.get(i));
  32.             dp[i][i] = result;
  33.         }
  34.         // 2 个数字到 N 个数字
  35.         for (int n = 2; n <= N; n++) {         //n代表每次处理字段的长度
  36.             for (int i = 0; i < N; i++) {     // 开始下标
  37.                 int j = i + n - 1;              // 结束下标
  38.                 if (j >= N) {                  //下标越界
  39.                     break;
  40.                 }
  41.                 ArrayList<Integer> result = new ArrayList<>();
  42.                 // 分成 i ~ s 和 s+1 ~ j 两部分，处理的字段，遍历字段起始到终止
  43.                 for (int s = i; s < j; s++) {
  44.                     ArrayList<Integer> result1 = dp[i][s];
  45.                     ArrayList<Integer> result2 = dp[s + 1][j];
  46.                     //分成两段的拼接
  47.                     for (int x = 0; x < result1.size(); x++) {
  48.                         for (int y = 0; y < result2.size(); y++) {
  49.                             // 第 s 个数字下标对应是第 s 个运算符
  50.                             char op = opList.get(s);
  51.                             result.add(caculate(result1.get(x), op, result2.get(y)));
  52.                         }
  53.                     }
  54.                 }
  55.                 dp[i][j] = result;
  57.             }
  58.         }
  59.         return dp[0][N-1];
  60.     }
  62.     //计算
  63.     private static int caculate(int num1, char c, int num2) {
  64.         switch (c) {
  65.             case '+':
  66.                 return num1 + num2;
  67.             case '-':
  68.                 return num1 - num2;
  69.             case '*':
  70.                 return num1 * num2;
  71.         }
  72.         return -1;
  73.     }
  75.     private static boolean isOperation(char c) {
  76.         return c == '+' || c == '-' || c == '*';
  77.     }
  78. }

解释：

ArrayList<Integer>[][] dp 是三维数组，可以利用ArrayList本身的特性来形式上降维。