HardArrayDynamic Programming

Burst Balloons

1 approach, code in every language

You are given n balloons in a row, each painted with a number stored in nums. You will burst all of them, one balloon per step.

When you burst the balloon at index i, you collect nums[left] * nums[i] * nums[right] coins, where left and right are the indices of the balloons still remaining directly beside i. If a neighbor no longer exists because it is off the ends of the row, treat its value as 1 (imagine an implicit balloon of value 1 padding both boundaries).

Return the maximum number of coins you can collect after every balloon has been burst.

Example 1

Input: nums = [3,1,5,8]

Output: 167

Bursting in the order 1, 5, 3, 8 yields 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.

Example 2

Input: nums = [1,5]

Output: 10

Burst 1 first for 1*1*5 = 5, then burst 5 for 1*5*1 = 5, totaling 10.

Constraints

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

Interval DP on the Last Balloon Burst

Pad the ends with 1s and let dp[l][r] be the best coins from the open interval (l, r), split by the balloon burst last.

Loading animation…

Intuition

Deciding which balloon to burst first is hard because it changes everyone's neighbors, so instead we reason about which balloon is burst last inside an interval. If balloon k is the last one popped in the open range (l, r), then when it pops its only surviving neighbors are the fixed boundaries l and r, earning nums[l] * nums[k] * nums[r]. Everything to the left of k and everything to the right of k are solved independently as smaller subproblems dp[l][k] and dp[k][r]. Padding nums with a 1 on both ends removes the special-casing for edge balloons. We fill the table by increasing interval length so both halves are ready when we combine them.

Algorithm walkthrough

1Build balloons = [1] + nums + [1] so index 0 and the last index act as boundary walls of value 1.
2Let dp[l][r] hold the maximum coins obtainable strictly between boundaries l and r (both exclusive).
3Iterate interval lengths from 2 upward; for each length choose the left boundary l and set r = l + length.
4For every k in (l, r), treat k as the last balloon popped: gain balloons[l]*balloons[k]*balloons[r] plus dp[l][k] and dp[k][r].
5Keep the maximum over all k in dp[l][r], and finally return dp[0][n-1] spanning the full padded array.

Implementation

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        balloons = [1] + nums + [1]
        n = len(balloons)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for l in range(0, n - length):
                r = l + length
                for k in range(l + 1, r):
                    coins = balloons[l] * balloons[k] * balloons[r]
                    dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + coins)
        return dp[0][n - 1]

Time

O(n^3)

Space

O(n^2)

There are O(n^2) intervals and each scans O(n) split points; the table stores one value per (l, r) pair.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Rail Disc Payout is our own problem on the technique behind Burst Balloons: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free