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 right are 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: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]
Return 167
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

Solution

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res(n+2, vector<int>(n+2, 0));
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        for ( int i = 1; i <= n; i++ ) {
            for ( int j = 1; j < n+2-i; j++ ) {
                // res[j][j+i-1]
                int tmp = 0;
                for ( int k = j; k <= j+i-1; k++ ) {
                    tmp = max(tmp, res[j][k-1] + res[k+1][j+i-1] + nums[k]*nums[j-1]*nums[j+i]);
                }
                res[j][j+i-1] = tmp;
            }
        }
        return res[1][n];
    }
};

Notes 很典型的Dynamic Programming的题目，但是一开始就没想到。（弱。。）
首先在原nums数组前后加上1来处理边界情况。用一个二维数组res来记录信息，res[i][j]表示打完nums[i]到nums[j]的最大得分。对于一个新的区间i to j，其子问题不外乎以下（j-i+1）种情况：

• 最后打nums[i]
• 最后打nums[i+1]
• .....
• 最后打nums[j].

最后打nums[k]的情况下，得分为：res[i][k-1] + res[k+1][j] + nums[i-1]*nums[k] + nums[j+1]. （因为两端增加了1，这里的边界情况可以很好地处理，而不用额外考虑。因为对任意i>j都有res[i][j] = 0。）