312. Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and rightare adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

用最簡單的想法想，每次選擇一個氣球弄爆得到分數，這樣會有n!種可能。但換個想法想，已經破掉的氣球就對後面的操作沒影響。但如果是考慮的前要爆破的氣球(假設氣球i)，那可以為總分增加nums[i - 1] * nums[i] * nums[i + 1]，但這樣等於三個數值都是不確定的會變動。如果逆著思考，從最後一個要爆破的氣球來計算，那麼假設在範圍[i, j]內挑選了一個k氣球當作最後一個要戳破的氣球，那麼最後一個氣球貢獻的得分就是nums[i -1] * nums[k] * nums[j + 1]，這時i -1和j + 1氣球是已知的而且固定在那，然後把[i, k - 1]和[k + 1, j]的結果加上就可。

// Top-Down Recursive DP with Memoization
int helper(vector<int>& nums, vector<vector<int> >& memo, int i, int j) {
    if (i > j) return 0;
    if (memo[i][j] > 0) return memo[i][j];
    int res = 0;
    for (int k = i; k <= j; ++k) {
        res = max(res, nums[i - 1] * nums[k] * nums[j + 1] + helper(nums, memo, i, k - 1) + helper(nums, memo, k + 1, j));
    }
    return memo[i][j] = res;
}
int maxCoins(vector<int>& nums) { // time: O(n^3); space: O(n^2)
    int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    vector<vector<int> > memo(n + 2, vector<int>(n + 2, 0));
    return helper(nums, memo, 1, n);
}

// Bottom-Up DP
int maxCoins(vector<int>& nums) { // time: O(n^3); space: O(n^2)
    int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            for (int k = i; k <= j; ++k) {
                dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
            }
        }
    }
    return dp[1][n];
}