分治 LeetCode241

描述

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

示例 1:

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

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

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

题解

据说应该使用分治
但整体很像矩阵链相乘算法
这个也按照别人的Python思路写了一遍
就是按照乘加符号分解为小问题。

挑战思路：如果不用递归怎么写？

中间查的内容：
1、C++如何将string转为int
已知 用iostream的方法，这个之前用过
atoi方法，但是好像最新的编译器才能用
2、substr(i,a),从i开始截取a长度。
abcde (0,2) 就是ab

class Solution {
public:

    
    vector<int> diffWaysToCompute(string input) {
        //让我想起了矩阵相乘问题 不过矩阵相乘不是动态规划问题吗
        //这个是怎么分治的
        //可能是分成？个运算符的问题
        //1、找到运算符的个数 2、运算符和运算数（感觉Python更好写？）
        //这个不能按照index直接分，因为可能为三位数字
        //按照符号分解为子问题
        vector<int>res;
        int index=0;       
        // printf("%s",input);
        for(int i=0;i<input.length();i++){
            if(input[i]=='+'||input[i]=='*'||input[i]=='-'){
                index+=1;
                vector<int> a;
                vector<int> b;
                a=diffWaysToCompute(input.substr(0,i));
                // printf("%s\n",input.substr(0,i).c_str());
            
                b=diffWaysToCompute(input.substr(i+1,input.length()-1-i));
                // printf("%s\n",input.substr(i+1,input.length()-1-i).c_str());
                for(int q=0;q<a.size();q++){
                    for(int p=0;p<b.size();p++){
                        if(input[i]=='+'){
                            res.push_back(a[q]+b[p]);
                        }
                        if(input[i]=='-'){
                             res.push_back(a[q]-b[p]);
                        }
                        if(input[i]=='*'){
                             res.push_back(a[q]*b[p]);
                        }
                        
                    }
                }

            }
        }
        if(index==0)
            res.push_back(atoi(input.c_str()));//string转int
        printf("%d",res[0]);
        return res;
    }
};