从Leetcode 每日一题练习继续讨论：
241. 为运算表达式设计优先级
241. Different Ways to Add Parentheses
题解
本题算是一道比较典型的递归加记忆化问题, 首先确定终止条件, 当某个子表达式中仅包含数字时, 则直接返回这个数字. 当是一个表达式时, 则分别递归计算运算符两侧的表达式可能得到的结果并根据运算符对两侧结果进行运算得到当前表达式所有可能得到的运算结果. 感觉和学习编译原理时经典的递归下降解析表达式的值有些相似.
举例来说, 对"2*3-4*5" 这样的式子, 我们只需将其看作不同表达式和运算符的组合, 分别计算这些表达式的值就能得出最终结果, 而计算表达式值的过程都是结构相似的问题, 因此可以不断分解成子问题. 这里就可以分解成2,*, 3-4*5. 即表达式2, 乘号以及后面的表达式. 也可以分解成2*3, -, 4*5. 这个分解可以用简单的字符串遍历来完成, 遍历整个表达式串, 遇到运算符则对运算符两侧的表达式进行递归求值, 继续遍历下一个运算符, 直到结尾.
显然这个过程中会有一些子表达式被重复计算, 因此可以想办法保存递归过程中算得的中间结果, 可以用一个二维数组表示从下标i开始到下标j的表达式的可能值. 即matrix[i][j]记录了i-j的表达式的所有可能运算结果. 二维数组可以使用一维数组表示, 即用i*length(表达式长度)+j来表示matrix[i][j]的值. 这样就可以用一个vector<vector>来表示记忆化的数组.
对于递归的问题, 思路一定要清楚, 只需找到递归的终止条件, 并写出解决最小的子问题的过程, 剩下的就是将问题分解, 分别使用递归求解分解后的问题再将结果整合起来进行处理, 至于中间递归的过程不要试图去想的太详细, 只要在宏观上能实现 分解问题->解决子问题->合并解决子问题的结果. 就能得到正确答案.
代码
class Solution {
public:
const int Big = 100000;
vector<int> diffWaysToCompute(string expression) {
int leng = expression.length();
vector<vector<int>> memo(leng*leng);
vector<int> result = subCompute(expression, 0, leng-1, memo, leng);
return result;
}
private:
vector<int> subCompute(const string& expression, int begin, int end, vector<vector<int>>& memo, int leng) {
if (memo[begin*leng+end].size() > 0) {
return memo[begin*leng+end];
}
vector<int> result;
bool hasOperator = false;
for (int i = begin; i <= end; i++) {
if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
hasOperator = true;
vector<int> left = subCompute(expression, begin, i-1, memo, leng);
vector<int> right = subCompute(expression, i+1, end, memo, leng);
for (int l : left) {
for (int r : right) {
if (expression[i] == '+') {
result.push_back(l + r);
} else if (expression[i] == '-') {
result.push_back(l - r);
} else if (expression[i] == '*') {
result.push_back(l * r);
}
}
}
}
}
if (!hasOperator) {
result.push_back(stoi(expression.substr(begin, end-begin+1)));
}
memo[begin*leng+end] = result;
return result;
}
};