Sweaty Imposter

Burst Balloons

HardDynamic Programming (1-D & 2-D)NeetCode 150SeniorOpen on LeetCodeUpdated

You're given n balloons in a row, balloon i painted with the number nums[i]. Bursting balloon i earns nums[left] * nums[i] * nums[right] coins, where left and right are the balloons currently next to it. A missing neighbor past either end counts as a balloon painted 1. After a burst, its two neighbors become adjacent. Return the maximum coins you can collect by bursting every balloon.

Examples

nums = [2,4,3] returns 33

Burst 4 first for 2 * 4 * 3 = 24, then 2 for 1 * 2 * 3 = 6, then 3 for 1 * 3 * 1 = 3, for 33 in total.

nums = [7] returns 7

The single balloon has the implied 1s on both sides: 1 * 7 * 1.

nums = [5,1,5] returns 55

Bursting the 1 first earns 25 and makes the two 5s neighbors, so the next burst earns 25 and the last earns 5.

Constraints

  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

Hints

Hint 1

If you pick the first balloon to burst, its neighbors become adjacent and the two sides interact. Is there a balloon in a range whose final neighbors you know for certain?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Each burst changes which balloons are adjacent, so the subproblems only separate cleanly when you choose the balloon in a range that bursts last. Pad nums with a 1 at each end, and let dp[l][r] be the most coins from bursting every balloon strictly between positions l and r. If k is the last balloon to go in that range, its neighbors at that moment are l and r themselves, so dp[l][r] = max over l < k < r of dp[l][k] + nums[l] * nums[k] * nums[r] + dp[k][r], and the two sides never interact. Fill by increasing gap r - l and return dp[0][n + 1]. O(n^3) time and O(n^2) space.

Time

O(n^3)

Space

O(n^2)

Pitfall

Splitting on the first balloon to burst. Removing it joins its left and right parts, so they aren't independent subproblems. Fix the last balloon in the range, whose neighbors are the range's fixed boundaries.

Solutions

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] v = new int[n + 2];
        v[0] = 1;
        v[n + 1] = 1;
        for (int i = 0; i < n; i++) v[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int gap = 2; gap <= n + 1; gap++) {
            for (int l = 0; l + gap <= n + 1; l++) {
                int r = l + gap;
                for (int k = l + 1; k < r; k++) {
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + v[l] * v[k] * v[r] + dp[k][r]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
Drill This