LeetCode 241. 为运算表达式设计优先级（动态规划）数据结构与算法Michael是个半路程序员-

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]; } };