Leetcode 312: Burst Balloons

 https://leetcode.com/problems/burst-balloons/description/

Notes:

This question is a very typical dp question. (in general, if a question can be down-size to a similar question, then it can be solved by dp)

One of the difficulties to this question is that the "boundary condition" is changing once we burst a balloon, since this balloon will disappear after the bursting.

One way to solve this is that: we can think about this question reversely. Instead of  starting from the first balloon to burst, we can start with the last balloon to burst.

The reason is that the last balloon will always has the fixed boundary condition. If we use dp[i][j] represents the maximum coins that we can obtained from [i, j] range, then

dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j])

where k in the range of [i, j].

To simplify the coding,, we can insert 1 in the begin and end of the original array, respectively.

The time complexity is O(N^3), and the space complexity if O(N^2).

See the code below:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // insert 1 in the begin and end of nums
        // i, j in the range of [1, n]
        // dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j])
        int n = nums.size();
        if(n==0) return 0;
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
        for(int i=1; i<n+1; ++i) dp[i][i] = nums[i-1]*nums[i]*nums[i+1];
        for(int i=n; i>0; --i) {
            for(int j=i+1; j<n+1; ++j) {
                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];
    }
};