Different Ways to Add Parenthese

题目来源
可以用划分的方法来做，就是每到一个符号，就把它割为两块，求出前面一块和后面一块的所有可能结果，然后再进行运算，代码如下：

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        int n = input.size();
        for (int i=0; i<n; i++) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*' ) {
                string part1 = input.substr(0, i);
                string part2 = input.substr(i+1);
                vector<int> res1 = diffWaysToCompute(part1);
                vector<int> res2 = diffWaysToCompute(part2);
                for (int num1 : res1)
                    for (int num2 : res2) {
                        if (input[i] == '+')
                            res.push_back(num1 + num2);
                        else if (input[i] == '-')
                            res.push_back(num1 - num2);
                        else
                            res.push_back(num1 * num2);
                    }
            }
        }
        if (res.empty())
            res.push_back(atoi(input.c_str()));
        return res;
    }
};

然后实际上计算过程中会有很多的重复计算，可以用DP来解决这个问题。

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        unordered_map<string, vector<int>> maps;
        res = computeWithDP(input, maps);
        return res;
    }
    
    vector<int> computeWithDP(string input, unordered_map<string, vector<int>> &maps)
    {
        if (maps.count(input) != 0)
            return maps[input];
        vector<int> res;
        int n = input.size();
        for (int i=0; i<n; i++) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*' ) {
                string part1 = input.substr(0, i);
                string part2 = input.substr(i+1);
                vector<int> res1 = diffWaysToCompute(part1);
                vector<int> res2 = diffWaysToCompute(part2);
                for (int num1 : res1)
                    for (int num2 : res2) {
                        if (input[i] == '+')
                            res.push_back(num1 + num2);
                        else if (input[i] == '-')
                            res.push_back(num1 - num2);
                        else
                            res.push_back(num1 * num2);
                    }
            }
        }
        if (res.empty())
            res.push_back(atoi(input.c_str()));
        return res;
    }
};