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;}elsenum = 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){ //按長度dpfor(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];} };

總結

以上是生活随笔為你收集整理的LeetCode 241. 为运算表达式设计优先级（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。