0312. Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

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

Example 1:

Input: nums = [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

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

• n == nums.length
• 1 <= n <= 500
• 0 <= nums[i] <= 100

Analysis

This is an "Interval DP" problem, which means you need to create a 2-d array to represent the optimal solution for each interval from start to end. Using dp[start][end] to represent the maximum value.

So for this problem, if nums = [3,1,5,8], then dp[1][4] is our solution.

Note

We use 1-based index for easy representation, because the boundary case of bursting the first or last balloon is easier to calculate. We just need to add two 1s to the beginning and the ending.

Next, we just need to try all the smaller segments first, then calculate the final answer.

First, we determine the length of each segment, and we start from len = 1, which means there is only one balloon, and ends at len = n.

Second, we determine the starting and ending points. We use i to represent the start and j to represent the end. Thus the range for start is from 1 to n-len+1, since we need to leave room for the ending. If we have determined our i, then our ending point is fixed, which is i+len-1.

Finally, we need to determine which balloon to burst from the i to j range. We use k to represent the bursting point, and we try all the possible points from k = i to k = j.

• Time: $O(n^3)$
• Space: $O(n^2)$ for the extra dp 2-d array

Code

class Solution {
public:

    int maxCoins(vector<int> &nums) {
        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];
    }
};