Burst Balloons
Hard · 2-D Dynamic Programming · Array · Dynamic Programming
Problem
There are n balloons in a row, and balloon i carries the number nums[i]. You must burst all of them, one at a time, in an order you choose.
Bursting balloon i earns left * nums[i] * right coins, where left and right are the numbers on the balloons currently next to it. After a balloon bursts, its two neighbors become next to each other. If a side has no balloon left, count it as a balloon marked 1.
Return the largest total number of coins you can collect.
Examples
Input: nums = [2,4,3] Output: 33
Burst 4 first (2 · 4 · 3 = 24), then 2 (1 · 2 · 3 = 6), then 3 (1 · 3 · 1 = 3): 33 in all.
Input: nums = [7] Output: 7
One balloon with a 1 on each side gives 1 · 7 · 1.
Input: nums = [1,5] Output: 10
Burst 1 first for 1 · 1 · 5 = 5, then 5 for 1 · 5 · 1 = 5.
Constraints
- n == len(nums)
- 1 <= n <= 300
- 0 <= nums[i] <= 100
Approaches
- Baseline: try every next balloon, memoized on the set left — time O(2^n · n²), space O(2^n)
Follow-up
The "pick the last event" trick fits any problem where an action merges or splits neighbors: cutting a stick at marks, triangulating a polygon, merging piles. Two of these are the use cases below. A greedy rule (burst the smallest first, or the largest last) fails on inputs as small as [3, 1, 5, 8].
Related problems
Start free on Cariara · Coding problems · System design studio
