給定一個(gè)含有數(shù)字和運(yùn)算符的字符串慷嗜，為表達(dá)式添加括號(hào)淀弹，改變其運(yùn)算優(yōu)先級(jí)以求出不同的結(jié)果。你需要給出所有可能的組合的結(jié)果庆械。有效的運(yùn)算符號(hào)包含 +, - 以及 * 薇溃。

示例 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

本題初看非常的復(fù)雜，但是細(xì)細(xì)分析缭乘，其實(shí)就是一道遞歸題沐序。
我們需要進(jìn)行分割運(yùn)算符兩邊來(lái)進(jìn)行遞歸。
每次遇見(jiàn)運(yùn)算符我們就計(jì)算兩邊的值，2* 3-45 可以被分為 2, 和3-45兩部分然后繼續(xù)分割策幼，當(dāng)出現(xiàn)全是數(shù)字的時(shí)候就不應(yīng)該再繼續(xù)分割了邑时，我們分割完了就需要合并，這個(gè)過(guò)程就是分治特姐，本題其實(shí)也用到分治算法的思想晶丘。

以2 * 3 - 4 * 5為例子， 我們分成 2 和 3 - 4 * 5唐含，再然后左邊不應(yīng)該再分了浅浮，我們分右邊，3 和 4 * 5 捷枯。 然后是 4 和 5滚秩。
最后我們進(jìn)行歸并，這就完了嗎淮捆？不是郁油，我們3 - 4 * 5不止一種分割方式，我們還可以 3 和 4先做減法攀痊，最后做乘法桐腌。
因此會(huì)得到兩個(gè)結(jié)果 一個(gè)是 (3-4)5 = -5 一個(gè)是 3- (45)=17，然后用2分別乘兩個(gè)數(shù)蚕苇，這樣就完成了第一次遞歸哩掺。
以此類推每次遇見(jiàn)運(yùn)算符就進(jìn)行遞歸即可。

• 我們會(huì)發(fā)現(xiàn)很多時(shí)候我們都會(huì)重復(fù)運(yùn)算涩笤，那么就進(jìn)行記憶化遞歸嚼吞，用空間換時(shí)間。
  代碼如下:

class Solution {
    
    Map <String,List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String input) {
        //處理當(dāng)input為空
        if (input.length() == 0){
            return new ArrayList<Integer>();
        }
        if(map.containsKey(input)){
            return map.get(input);
        }
        //處理全數(shù)字
        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;
        };
        //當(dāng)有運(yùn)算符
        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;
    }
}

既然我們都想到了可以用記憶化遞歸蹬碧，那我們同樣也可以用動(dòng)態(tài)規(guī)劃來(lái)做本題舱禽，我一開(kāi)始根本沒(méi)往這方面想過(guò)，看了題解才想到的恩沽，但是確實(shí)記憶化遞歸一般都可以用效率更佳的動(dòng)歸來(lái)解決誊稚。

動(dòng)歸的難點(diǎn)就在于dp數(shù)組到底應(yīng)該放什么，按照道理來(lái)說(shuō)應(yīng)該是放各個(gè)子集罗心，然后保存一個(gè)最終答案里伯，那應(yīng)該怎么放呢。
我們是設(shè)置一個(gè)dp[N][N]的數(shù)組渤闷，N為數(shù)字的個(gè)數(shù)疾瓮，我們最終返回dp[0][N]，這是從0到第N個(gè)數(shù)的所有可能性的集合飒箭，那顯然dp[0][0],dp[1][1] ......就是分別為第一個(gè)數(shù)字狼电，第二個(gè)數(shù)字蜒灰，然后dp[0][1]就是第一個(gè)數(shù)字和第二個(gè)數(shù)字運(yùn)算得到的結(jié)果，dp[0][2]就是前三個(gè)數(shù)字運(yùn)算得到的結(jié)果肩碟。
這樣做的一個(gè)問(wèn)題就在于我們需要提前處理强窖，將運(yùn)算符和數(shù)字給分離出來(lái)，再根據(jù)長(zhǎng)度進(jìn)行對(duì)dp數(shù)組的填充削祈。

• 本題動(dòng)歸的思想是比較難想到的翅溺，主要是通過(guò)遞歸記憶法聯(lián)想而到。
  代碼如下:

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為長(zhǎng)度
        for(int i = 2; i <= N; i++ ){
            //m為開(kāi)始下標(biāo)
            for(int m = 0; m < N; m++){
                //j為結(jié)束下標(biāo)
                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;
    }

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有岩瘦。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)未巫，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處窿撬。