題目

241. Different Ways to Add Parentheses
難度: 中等，但我覺得爆難

題意

給定一字串expression，字串中由數字字元及操作元(operator)'+', '-', '*'組成。
操作元可任意發生順序，求所有的計算結果。
範例1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

範例2
Input: expression = "23-45"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

思路

仔細觀察其中一個op:
(左邊所有組合)op(右邊所有組合)
若左右為已知答案，只要兩邊的組合交叉操作一下op，不就得到當前此op的所有答案了嗎~
這種透過子集合的答案求解的題型，最適合使用動態規劃了。
只是這題必須存下左邊所有組合以及又邊所有組合，只能出動三維動態陣列來存。

首先，先切割expression如下:
num[0] op[0] num[1] op[1] ... num[n - 1] op[n - 1] num[n]

設dp[i][j]為一整數陣列，存入num[i]到num[j]的所有可能的解。
初始化所有dp[x][x]，x~x的組合就是num[x]
(左邊所有組合)op(右邊所有組合)可以透過遍歷left, medium, right邊界來取得。

要注意，因為一開始只會初始化dp[x][x]，因此其他地方都是空陣列，因此必須先從left subarray長度為1開使增長羅列。在這邊卡超級久。

實作

class Solution
{
private:
    int compute(int a, int b, char op)
    {
        if (op == '+')
            return a + b;
        else if (op == '-')
            return a - b;
        else if (op == '*')
            return a * b;
        // Prevent non-void function
        return -1;
    }

public:
    vector<int> diffWaysToCompute(string expression)
    {
        istringstream iss(expression);
        int num;
        char op;
        vector<int> num_arr;
        vector<char> op_arr;
        while (iss >> num)
        {
            num_arr.push_back(num);
            if (iss >> op)
                op_arr.push_back(op);
        }

        const int n = (int) num_arr.size();
        // dp[i][j] stores all results from num[i] to num[j]
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n));

        for (int i = 0; i < n; i++)
            dp[i][i].push_back(num_arr[i]);

        // Iterate possible length of left subarray
        for (int len = 0; len < n; len++)
        {
            // Iterate possible right bound of left subarray
            for (int l = 0; l < n - len; l++)
            {
                // Iterate possible right bound of left subarray
                for (int m = l; m < l + len; m++)
                {
                    // Possible solutions
                    for (int l_sol : dp[l][m])
                        for (int r_sol : dp[m + 1][l + len])
                            dp[l][l + len].push_back(
                                compute(l_sol, r_sol, op_arr[m]));
                }
            }
        }

        // Sort if needed
        sort(dp[0][n - 1].begin(), dp[0][n - 1].end());
        return dp[0][n - 1];
    }
};

分析

(不確定分析對不對)
設num數量為N
時間複雜度: O(N^2)，主要是possible solution的地方需要N * N?
空間複雜度: O(N^2 * N !)，DP表大小N * N，每隔存最多N!個

結果

第一次submit，沒有把return function寫完，領了一個CE。

int compute(int a, int b, char op)
{
    if (op == '+')
        return a + b;
    else if (op == '-')
        return a - b;
    else if (op == '*')
        return a * b;
}

第二次submit結果
Accepted
25/25 cases passed (3 ms)
Your runtime beats 63.55 % of cpp submissions
Your memory usage beats 99.67 % of cpp submissions (8 MB)