题目描述（中等难度）

241. Different Ways to Add Parentheses - 图1

给一个表达式加括号，得到所有不同情况的解。

解法一 递归

一看到题就觉得有点复杂，可以考虑一下递归的方式，去寻找子问题和原问题解的关系。

可以通过运算符把整个式子分成两部分，两部分再利用递归解决。

以 2 * 3 - 4 * 5 为例。

2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 * 3 和 4 * 5 两部分，中间是 - 号相连。

2 * 3 - 4 和 5 两部分，中间是 * 号相连。

有了两部分的结果，然后再通过中间的符号两两计算加入到最终的结果中即可。

比如第一种情况，2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 的解就是 [2]，3 - 4 * 5 的解就是 [-5, -17]。

把两部分解通过 * 号计算，最终结果就是 [-10, -34]。

另外两种情况也类似。

然后还需要递归出口。

如果给定的字符串只有数字，没有运算符，那结果就是给定的字符串转为数字。

比如上边的第一种情况，2 的解就是 [2]。

  1. public List<Integer> diffWaysToCompute(String input) {
  2.     if (input.length() == 0) {
  3.         return new ArrayList<>();
  4.     }
  5.     List<Integer> result = new ArrayList<>();
  6.     int num = 0;
  7.     //考虑是全数字的情况
  8.     int index = 0;
  9.     while (index < input.length() && !isOperation(input.charAt(index))) {
  10.         num = num * 10 + input.charAt(index) - '0';
  11.         index++;
  12.     }
  13.     //将全数字的情况直接返回
  14.     if (index == input.length()) {
  15.         result.add(num);
  16.         return result;
  17.     }
  19.     for (int i = 0; i < input.length(); i++) {
  20.         //通过运算符将字符串分成两部分
  21.         if (isOperation(input.charAt(i))) {
  22.             List<Integer> result1 = diffWaysToCompute(input.substring(0, i));
  23.             List<Integer> result2 = diffWaysToCompute(input.substring(i + 1));
  24.             //将两个结果依次运算
  25.             for (int j = 0; j < result1.size(); j++) {
  26.                 for (int k = 0; k < result2.size(); k++) {
  27.                     char op = input.charAt(i);
  28.                     result.add(caculate(result1.get(j), op, result2.get(k)));
  29.                 }
  30.             }
  31.         }
  32.     }
  33.     return result;
  34. }
  36. private int caculate(int num1, char c, int num2) {
  37.     switch (c) {
  38.         case '+':
  39.             return num1 + num2;
  40.         case '-':
  41.             return num1 - num2;
  42.         case '*':
  43.             return num1 * num2;
  44.     }
  45.     return -1;
  46. }
  48. private boolean isOperation(char c) {
  49.     return c == '+' || c == '-' || c == '*';
  50. }

由于递归是两个分支，所以会有一些的解进行了重复计算，我们可以通过 memoization 技术，前边很多题都用过了，一种空间换时间的方法。

将递归过程中的解保存起来，如果第二次递归过来，直接返回结果即可，无需重复递归。

将解通过 map 存储，其中，key 存储函数入口参数的字符串，value 存储当前全部解的一个 List 。

  1. //添加一个 map
  2. HashMap<String,List<Integer>> map = new HashMap<>();
  3. public List<Integer> diffWaysToCompute(String input) {
  4.     if (input.length() == 0) {
  5.         return new ArrayList<>();
  6.     }
  7.     //如果已经有当前解了，直接返回
  8.     if(map.containsKey(input)){
  9.         return map.get(input);
  10.     }
  11.     List<Integer> result = new ArrayList<>();
  12.     int num = 0;
  13.     int index = 0;
  14.     while (index < input.length() && !isOperation(input.charAt(index))) {
  15.         num = num * 10 + input.charAt(index) - '0';
  16.         index++;
  17.     }
  18.     if (index == input.length()) {
  19.         result.add(num);
  20.         //存到 map
  21.         map.put(input, result);
  22.         return result;
  23.     }
  24.     for (int i = 0; i < input.length(); i++) {
  25.         if (isOperation(input.charAt(i))) {
  26.             List<Integer> result1 = diffWaysToCompute(input.substring(0, i));
  27.             List<Integer> result2 = diffWaysToCompute(input.substring(i + 1));
  28.             for (int j = 0; j < result1.size(); j++) {
  29.                 for (int k = 0; k < result2.size(); k++) {
  30.                     char op = input.charAt(i);
  31.                     result.add(caculate(result1.get(j), op, result2.get(k)));
  32.                 }
  33.             }
  34.         }
  35.     }
  36.      //存到 map
  37.     map.put(input, result);
  38.     return result;
  39. }
  41. private int caculate(int num1, char c, int num2) {
  42.     switch (c) {
  43.         case '+':
  44.             return num1 + num2;
  45.         case '-':
  46.             return num1 - num2;
  47.         case '*':
  48.             return num1 * num2;
  49.     }
  50.     return -1;
  51. }
  53. private boolean isOperation(char c) {
  54.     return c == '+' || c == '-' || c == '*';
  55. }

解法二 动态规划

按理说写完递归、 写完 memoization ，接下来动态规划也能顺理成章的写出来了，比如经典的 爬楼梯 问题。但这个如果什么都不处理，dp 数组的含义比较难定义，分享一下 这里 的处理吧。

最巧妙的地方就是做一个预处理，把每个数字提前转为 int 然后存起来，同时把运算符也都存起来。

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

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

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

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

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

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

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

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

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

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

  1. 2 * 3 - 4 * 5
  2. 存起来的数字是 numList = [2 3 4 5]，
  3. 存起来的运算符是 opList = [*, -, *]。
  5. 假设我们求 dp[1][3]
  6. 也就是计算 3 - 4 * 5 的解
  7. 分成 3 和 4 * 5 两部分，3 对应的下标是 1 ，对应的运算符就是 opList[1] = '-' 。
  8. 也就是计算 3 - 20 = -17
  10. 分成 3 - 4 和 5 两部分，4 的下标是 2 ，对应的运算符就是 opList[2] = '*'。
  11. 也就是计算 -1 * 5 = -5
  13. 所以 dp[1][3] = [-17 -5]

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

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

  1. public List<Integer> diffWaysToCompute(String input) {
  2.     List<Integer> numList = new ArrayList<>();
  3.     List<Character> opList = new ArrayList<>();
  4.     char[] array = input.toCharArray();
  5.     int num = 0;
  6.     for (int i = 0; i < array.length; i++) {
  7.         if (isOperation(array[i])) {
  8.             numList.add(num);
  9.             num = 0;
  10.             opList.add(array[i]);
  11.             continue;
  12.         }
  13.         num = num * 10 + array[i] - '0';
  14.     }
  15.     numList.add(num);
  16.     int N = numList.size(); // 数字的个数
  18.     // 一个数字
  19.     ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];
  20.     for (int i = 0; i < N; i++) {
  21.         ArrayList<Integer> result = new ArrayList<>();
  22.         result.add(numList.get(i));
  23.         dp[i][i] = result;
  24.     }
  25.     // 2 个数字到 N 个数字
  26.     for (int n = 2; n <= N; n++) {
  27.         // 开始下标
  28.         for (int i = 0; i < N; i++) {
  29.             // 结束下标
  30.             int j = i + n - 1;
  31.             if (j >= N) {
  32.                 break;
  33.             }
  34.             ArrayList<Integer> result = new ArrayList<>();
  35.             // 分成 i ~ s 和 s+1 ~ j 两部分
  36.             for (int s = i; s < j; s++) {
  37.                 ArrayList<Integer> result1 = dp[i][s];
  38.                 ArrayList<Integer> result2 = dp[s + 1][j];
  39.                 for (int x = 0; x < result1.size(); x++) {
  40.                     for (int y = 0; y < result2.size(); y++) {
  41.                         // 第 s 个数字下标对应是第 s 个运算符
  42.                         char op = opList.get(s);
  43.                         result.add(caculate(result1.get(x), op, result2.get(y)));
  44.                     }
  45.                 }
  46.             }
  47.             dp[i][j] = result;
  49.         }
  50.     }
  51.     return dp[0][N-1];
  52. }
  54. private int caculate(int num1, char c, int num2) {
  55.     switch (c) {
  56.         case '+':
  57.             return num1 + num2;
  58.         case '-':
  59.             return num1 - num2;
  60.         case '*':
  61.             return num1 * num2;
  62.     }
  63.     return -1;
  64. }
  66. private boolean isOperation(char c) {
  67.     return c == '+' || c == '-' || c == '*';
  68. }

总

解法一的话是比较直觉的方法，用递归可以将问题简化。

解法二的话，关键就在于字符串的预处理，将数字和运算符分别存起来，很巧妙。然后就能很明确的定义出 dp 的含义，代码就比较容易写出来了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情