1. 解题
给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。
你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 *
。
示例 1:
输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. DP解题
-
dp[i][j]
存储区间[i,j]
内可能的结果数值 - 先初始化
dp[i][i],dp[i][i+1]
- 然后按照区间长度 len 不断加大
dp[i][i+len] = sum(dp[i][j] op dp[j+1][i+len])
j 在区间内遍历,左右的数组合进行运算的值,存入dp[i][i+len]
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
int i, j, k, num=0;
vector<int> arr;//数字存起来
vector<char> op;//操作符存起来
for(i = 0; i < input.size(); ++i)
{
if(!isdigit(input[i]))
{
arr.push_back(num);
op.push_back(input[i]);
num = 0;
}
else
num = num*10+input[i]-'0';
}
arr.push_back(num);//最后一个数字
int n = arr.size();
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n));
for(i = 0; i < n-1; ++i)
{
dp[i][i] = {arr[i]};//初始化dp[i][i]
if(op[i]=='+')
dp[i][i+1] = {arr[i]+arr[i+1]};//初始化dp[i][i+1]
else if(op[i]=='-')
dp[i][i+1] = {arr[i]-arr[i+1]};
else if(op[i]=='*')
dp[i][i+1] = {arr[i]*arr[i+1]};
}
dp[n-1][n-1] = {arr[n-1]};//初始化dp[i][i]
for(int len = 2; len < n; ++len)
{ //按长度dp
for(i = 0; i < n-len; ++i)
{ //左端点
for(j = i; j < i+len; ++j)
{ //中间端点
for(int dl : dp[i][j])
{ //左边的数值
for(int dr : dp[j+1][i+len])//左边的数值
if(op[j]=='+')
dp[i][i+len].push_back(dl+dr);
else if(op[j]=='-')
dp[i][i+len].push_back(dl-dr);
else if(op[j]=='*')
dp[i][i+len].push_back(dl*dr);
}
}
}
}
sort(dp[0][n-1].begin(),dp[0][n-1].end());
return dp[0][n-1];
}
};