LeetCode241. 为运算表达式设计优先级 - 分治法

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4 。

示例 1：

输入：expression = “2-1-1”
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：

输入：expression = “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

提示：

1 <= expression.length <= 20
expression 由数字和算符 ‘+’、‘-’ 和 ‘*’ 组成。
输入表达式中的所有整数值在范围 [0, 99]

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

class Solution {
public:
    unordered_map> mp;            //优化 记忆化搜索
    vector diffWaysToCompute(string expression) {
        //方法1 分治法+dfs+记忆化+序列化 O(2^n) O(2^n) 
        //本质上是个分治，其实就是大问题划分为左右两个子问题，然后不断通过后序遍历的方式去求解，求解过程中发现存在之前计算过的小问题，可以使用map进行记录，避免重复计算
        // 结果种类其实是一个 卡特兰数，可以看作 运算符的入栈出栈顺序

        int n=expression.length();
        return dfs(expression,0,n);

        //方法2 动态规划（区间DP) 三维向量 用dp[i][j]来存储字符串 [i,j)时 所有可能结果的向量即可
    }
    vector dfs(string expression,int beg,int n){
        vector ret;                            //记录答案
        int f=0;                                    //判断是否有运算符号 (可以省略 如用ret判空来代替)
        for(int i=beg;i l=mp.count(to_string(beg)+" "+to_string(i))==1?mp[to_string(beg)+" "+to_string(i)]:dfs(expression,beg,i);                                   
                vector r=mp.count(to_string(i+1)+" "+to_string(n))==1?mp[to_string(i+1)+" "+to_string(n)]:dfs(expression,i+1,n);
                for(auto a:l){                      //进行两轮遍历 来进行组和
                    for(auto b:r){
                        if(expression[i]=='+') ret.push_back(a+b);
                        else if(expression[i]=='-') ret.push_back(a-b);
                        else ret.push_back(a*b);
                    }
                }
            }
        }
        if(f==0) ret.push_back(stoi(expression.substr(beg,n-beg))); //没有运算符号 即子串本身是一个数字(也可以遍历字符串来转成数字)
        // if(ret.empty()){
        //     int temp=0;
        //     for(int i=beg;i