Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:

Input: "23-45"
Output: [-34, -14, -10, -10, 10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

我的答案：先把数字和符号存到两个vector里面，然后要recursion，recursion有重复所以用dp，这里这个dp是3重vector，空间复杂度可能是O(n^2 * ans_size), ans_size可能是O(n^2) （算不清楚了，晕），总之空间复杂度很高，写的时候特别怕。结果出人意料的好。

class Solution {
private:
    vector<vector<vector<int>>> val_dp;
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> nums;
        vector<char> symbols{'+'};
        
        int len = input.size();
        int num = 0;
        for (int i=0; i<len; ++i) {
            char c = input[i];
            if (isdigit(c))
                num = num*10 + (c-'0');
            else {
                nums.push_back(num);
                symbols.push_back(c);
                num = 0;
            }
        }
        nums.push_back(num);
        
        len = nums.size();
        val_dp = vector<vector<vector<int>>>(len, vector<vector<int>>(len, vector<int>()));
        vector<int> ans = dp(0, len, nums, symbols);

        return ans;
    }
    
    vector<int> dp(int start, int end, const vector<int>& nums, const vector<char>& symbols) {
        if (start == end)
            return {};
        if (start+1 == end)
            return {nums[start]};
        if (val_dp[start][end-1].size() > 0)
            return val_dp[start][end-1];
        
        vector<int> ret, left, right;
        for (int i=start+1; i<end; ++i) {
            if (val_dp[start][i-1].size() == 0) {
                left = dp(start, i, nums, symbols);
                val_dp[start][i-1] = left;
            }
            else
                left = val_dp[start][i-1];
            
            if (val_dp[i][end-1].size() == 0) {
                right = dp(i, end, nums, symbols);
                val_dp[i][end-1] = right;
            }
            else
                right = val_dp[i][end-1];
            
            // cout << left.size() << " - " << right.size() << endl;
            for (const auto& l : left) {
                for (const auto& r : right) {
                    if (symbols[i] == '+')
                        ret.push_back(l+r);
                    else if (symbols[i] == '-')
                        ret.push_back(l-r);
                    else
                        ret.push_back(l*r);
                }
            }
        }
        val_dp[start][end-1] = ret;
        return ret;
    }
};

Runtime: 4 ms, faster than 80.93% of C++ online submissions for Different Ways to Add Parentheses.
Memory Usage: 7.4 MB, less than 88.38% of C++ online submissions for Different Ways to Add Parentheses.