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

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

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:

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

本题初看非常的复杂，但是细细分析，其实就是一道递归题。
我们需要进行分割运算符两边来进行递归。
每次遇见运算符我们就计算两边的值，2* 3-45 可以被分为 2, 和3-45两部分然后继续分割，当出现全是数字的时候就不应该再继续分割了，我们分割完了就需要合并，这个过程就是分治，本题其实也用到分治算法的思想。

以2 * 3 - 4 * 5为例子，我们分成 2 和 3 - 4 * 5，再然后左边不应该再分了，我们分右边，3 和 4 * 5 。然后是 4 和 5。
最后我们进行归并，这就完了吗？不是，我们3 - 4 * 5不止一种分割方式，我们还可以 3 和 4先做减法，最后做乘法。
因此会得到两个结果一个是 (3-4)5 = -5 一个是 3- (45)=17，然后用2分别乘两个数，这样就完成了第一次递归。
以此类推每次遇见运算符就进行递归即可。

我们会发现很多时候我们都会重复运算，那么就进行记忆化递归，用空间换时间。
代码如下:

class Solution {
    
    Map <String,List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String input) {
        //处理当input为空
        if (input.length() == 0){
            return new ArrayList<Integer>();
        }
        if(map.containsKey(input)){
            return map.get(input);
        }
        //处理全数字
        int index = 0;
        int num = 0;
        List<Integer> result = new ArrayList<>();
        while (index < input.length() && !isOperation(input.charAt(index)) ){
            num = num * 10 + (input.charAt(index) - '0');
            index++;
        }
        if (index == input.length()){
            result.add(num);
            map.put(input,result);
            return result;
        };
        //当有运算符
        for (int i = 0; i < input.length(); i++){
            if(isOperation(input.charAt(i))){
                List<Integer> list1 = diffWaysToCompute(input.substring(0,i));
                List<Integer> list2 = diffWaysToCompute(input.substring(i+1,input.length()));

                for(int m = 0; m < list1.size(); m++)
                    for( int n = 0; n < list2.size(); n++)
                     result.add(Compute(list1.get(m),list2.get(n),input.charAt(i)));           
           
            }   
        }
        map.put(input,result);
        return result;
    }

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

    int Compute (int num1, int num2, char op){
        int ans = 0;
        switch(op){
            case '+': ans = num1 + num2; break; 
            case '-': ans = num1 - num2; break; 
            case '*': ans = num1 * num2; break; 
        }
        return ans;
    }
}

既然我们都想到了可以用记忆化递归，那我们同样也可以用动态规划来做本题，我一开始根本没往这方面想过，看了题解才想到的，但是确实记忆化递归一般都可以用效率更佳的动归来解决。

动归的难点就在于dp数组到底应该放什么，按照道理来说应该是放各个子集，然后保存一个最终答案，那应该怎么放呢。
我们是设置一个dp[N][N]的数组，N为数字的个数，我们最终返回dp[0][N]，这是从0到第N个数的所有可能性的集合，那显然dp[0][0],dp[1][1] ......就是分别为第一个数字，第二个数字，然后dp[0][1]就是第一个数字和第二个数字运算得到的结果，dp[0][2]就是前三个数字运算得到的结果。
这样做的一个问题就在于我们需要提前处理，将运算符和数字给分离出来，再根据长度进行对dp数组的填充。

本题动归的思想是比较难想到的，主要是通过递归记忆法联想而到。
代码如下:

class Solution {
    
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> nums = new ArrayList<>();
        List<Character> ops = new ArrayList<>();
        int num = 0;
        for (int i = 0; i < input.length(); i++){
            if(isOperation(input.charAt(i))){
                nums.add(num);
                num = 0;
                ops.add(input.charAt(i));
            }
            else{
                num = num * 10 + (input.charAt(i) - '0');
            }
        }
        nums.add(num);
        int N = nums.size();
        ArrayList<Integer>[][] dp= new ArrayList[N][N];
        //base
        for(int i = 0; i < N ; i++){
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(nums.get(i));
            dp[i][i]=temp;
        }
        //i为长度
        for(int i = 2; i <= N; i++ ){
            //m为开始下标
            for(int m = 0; m < N; m++){
                //j为结束下标
                int j = m + i - 1;
                if( j >= N )
                    break;

                ArrayList<Integer> result = new ArrayList<>();
                for (int s = m; s < j; s++){
                    ArrayList<Integer> list1 = dp[m][s];
                    ArrayList<Integer> list2 = dp[s+1][j];
            
                    for (int p = 0; p < list1.size(); p++){
                        for (int q = 0; q < list2.size(); q++){
                            result.add(Compute(list1.get(p),list2.get(q),ops.get(s)));
                        }
                    }
                }
                dp[m][j] = result;
            }
        }
        return dp[0][N-1];
    }

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

    int Compute (int num1, int num2, char op){
        int ans = 0;
        switch(op){
            case '+': ans = num1 + num2; break; 
            case '-': ans = num1 - num2; break; 
            case '*': ans = num1 * num2; break; 
        }
        return ans;
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。