【Leetcode】241. 为运算表达式设计优先级

241. 为运算表达式设计优先级（中等）

解法一：分治法

对于这道题，加括号其实就是决定运算次序，所以我们可以把加括号转化为，「对于每个运算符号，先执行处理两侧的数学表达式，再处理此运算符号」。

对于一个形如 x op y 的算式而言，它的结果组合取决于 x 和 y 的结果组合数 ，而 x 和 y 又可以写成形如 x op y 的算式。

因此，该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解 。

对于分治算法分成三步走：

• 分解：按照运算符分隔成左右两部分，分别求解；
• 解决：通过递归实现，最终我们会得到只包含数字的算式，返回数字作为算式解；
• 合并：根据运算符合并左右两部分的解，得出最终解。

代码

class Solution {
public:vector<int> diffWaysToCompute(string expression) {vector<int> ans, left, right;int flag = 0; int n = expression.size();for(int i=0; i<n; ++i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag = 1; // flag=1说明string是表达式，flag=0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left = diffWaysToCompute(string(expression, 0, i));right = diffWaysToCompute(string(expression, i+1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] == '+') ans.push_back(l + r);if(expression[i] == '-') ans.push_back(l - r);if(expression[i] == '*') ans.push_back(l * r);}}}}if(flag == 0){// expression 只是一个数字// {int} -> vector<int>return {stoi(expression)};}return ans;}
};

解法二：分治法+记忆化

解法一中存在重复运算，比如 2*3 - 4*5 ，按照第一个 * 分割，右边部分是 3 - 4*5 ，进而计算 4*5 ，而按照 - 分割，同样会再次计算 4*5 。

为了减少重复运算，可以使用记忆化搜索，保存字符串区间[l,r]的运算结果，整个思路和解法一类似，不同点在于：设置一个 map 保存结果，递归的时候先在 map 中查找，如果该字符串已经计算过，那么直接返回保存的结果。

代码

class Solution {
public:unordered_map<string, vector<int>> mp;vector<int> diffWaysToCompute(string expression) {if(mp.find(expression) != mp.end()) return mp.find(expression) -> second;vector<int> ans, left, right;int flag = 0; int n = expression.size();for(int i=0; i<n; ++i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag = 1; // flag=1说明string是表达式，flag=0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left = diffWaysToCompute(string(expression, 0, i));right = diffWaysToCompute(string(expression, i+1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] == '+') ans.push_back(l + r);if(expression[i] == '-') ans.push_back(l - r);if(expression[i] == '*') ans.push_back(l * r);}}}}if(flag == 0){// expression 只是一个数字// {int} -> vector<int>return {stoi(expression)};}mp[expression] = ans;return ans;}
};

解法三：动态规划

对于表达式 expression 需要做预处理：「把每个数字转为 int 存起来，同时运算符也存起来」。

这样子将得到两个数组，以 2 * 3 - 4 * 5 为例，存起来的数字是 numList = [2 3 4 5]，存起来的运算符是 opList = [*, -, *]。

状态定义

dp[i][j] 表示从第 i 个数字到第 j 个数字（从 0 开始计数）范围内表达式的所有解。

如 dp[1][3]表示：第 1 个数字 （3） 到 第 3 个数字（5）范围内表达式 3 - 4 * 5 的所有解。

状态转移方程

有了一个数字的所有解（初始化），就可以求出两个数字的所有解。

有了两个数字的所有解，三个数字的所有解就和解法一求法一样。

把三个数字分成两部分，将两部分的解两两组合起来即可。

对于两部分之间的运算符，因为表达式是一个数字一个运算符，所以运算符的下标就是左部分最后一个数字的下标。

对于 2 * 3 - 4 * 5 ，存起来的数字是 numList = [2 3 4 5]， 存起来的运算符是 opList = [*, -, *]。

假设要求 dp[1][3]，也就是计算 3 - 4 * 5 的解：

• 分成 3 和 4 * 5 两部分，3 对应的下标是 1 ，对应的运算符就是 opList[1] = '-' ，也就是计算 3 - 20 = -17；

• 分成 3 - 4 和 5 两部分，4 的下标是 2 ，对应的运算符就是 opList[2] = '*'。
  也就是计算 -1 * 5 = -5

• 所以 dp[1][3] = [-17 -5] 。

四个、五个… 都可以分成两部分，然后通过之前的解求出来。

直到包含了所有数字的解求出来。

初始化

对范围内只有一个数字的情况进行初始化：

dp[0][0] = 2, dp[1][1] = 3, dp[2][2] = 4, dp[3][3] = 5;

返回的最终结果

最终返回第 0 个数字到最后一个数字范围内表达式的所有解，即 dp[0][n-1]；

代码

class Solution {
public:vector<int> diffWaysToCompute(string expression) {vector<int>  numList;vector<char> opList;// 对 expression 预处理int num = 0;for(char ch : expression){if(!isdigit(ch)){numList.push_back(num);num = 0;opList.push_back(ch);}else{num = num * 10 + ch - '0';}}numList.push_back(num);int n = numList.size();vector<vector<vector<int>>> dp(n, vector<vector<int>>(n));// dp数组初始化for(int i=0; i<n; ++i){dp[i][i].push_back(numList[i]);}// 从2个数字遍历到n个数字for(int k=2; k<=n; ++k){// 开始遍历的下标for(int i=0; i<n; ++i){// 结束遍历的下标int j = i + k - 1;if(j >= n){// 越界break;}vector<int> ans;// 以s作为分隔点分成左右两部分遍历for(int s=i; s<j; ++s){vector<int> left = dp[i][s];vector<int> right = dp[s+1][j];// 遍历左边部分的所有结果值for(auto x : left){// 遍历右边部分的所有结果值for(auto y : right){// 根据操作符对所有结果进行组合// 操作符下标就是左边部分最后一个数字的下标char op = opList[s];if(op == '+') ans.push_back(x + y);else if(op == '-') ans.push_back(x - y);else if(op == '*') ans.push_back(x * y);}}}dp[i][j] = ans;}}return dp[0][n-1];}
};