Burst Balloons
Solve this Problemnums balloons lined up in a row, bursting balloon i earns left · nums[i] · right coins, where left and right are whatever balloons currently sit next to it at the moment it's burst (treat both ends of the row as an invisible balloon of value 1 once nothing real is left there). After a balloon bursts, its former neighbors become adjacent to each other. Burst every balloon, in whichever order earns the most total coins.
The trap is thinking forward — simulating each burst changes the neighbor relationships for every burst after it, so tracking "who's next to whom" gets tangled fast. Thinking about which balloon gets burst *last* inside a shrinking range sidesteps that entirely: whatever's left just outside that range are that balloon's guaranteed final neighbors, since everything else inside the range is already gone by the time it's its turn. That reframes the whole problem as picking, independently for every possible sub-range, which balloon is the last survivor there — exactly the kind of overlapping-subproblem structure interval DP is built for.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 300 - ◆
0 ≤ nums[i] ≤ 100
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive, Burst the Last Balloon First
BruteSimulating the bursts in the order they actually happen is messy — every burst changes who's adjacent to whom next. The fix is to think backwards: for any range of balloons still standing, ask which one will be the *last* one burst inside that range. Whichever it is, that balloon's final neighbors are whatever's just outside the range on each side (everything else inside the range is already gone by then), so its payout is fixed and known up front. Trying every balloon as that "last one" and recursing on the two independent sub-ranges it leaves behind turns a stateful simulation into a clean recursion — at the cost of re-deriving the same sub-range's answer through many different outer choices.
O(2ⁿ)O(n)1class Solution {
2 private int[] a;
3
4 public int maxCoins(int[] nums) {
5 int n = nums.length;
6 a = new int[n + 2];
7 a[0] = 1;
8 a[n + 1] = 1;
9 for (int i = 0; i < n; i++) a[i + 1] = nums[i];
10 return solve(0, n + 1);
11 }
12
13 private int solve(int left, int right) {
14 if (left + 1 == right) return 0;
15 int best = 0;
16 for (int k = left + 1; k < right; k++) {
17 int coins = solve(left, k) + solve(k, right) + a[left] * a[k] * a[right];
18 if (coins > best) best = coins;
19 }
20 return best;
21 }
22}Optimal — Bottom-Up Interval DP
OptimalThe same "last balloon burst in this range" idea works bottom-up: pad the array with a virtual 1 on each side, then fill a table dp[left][right] = the best payout for bursting every balloon strictly between positions left and right, processing ranges from the smallest gap outward. Once dp is known for every shorter range, dp[left][right] just picks the best of a[left]·a[k]·a[right] + dp[left][k] + dp[k][right] over every candidate last balloon k — no range is ever solved twice.
O(n³)O(n²)1class Solution {
2 public int maxCoins(int[] nums) {
3 int n = nums.length;
4 int[] a = new int[n + 2];
5 a[0] = 1;
6 a[n + 1] = 1;
7 for (int i = 0; i < n; i++) a[i + 1] = nums[i];
8 int[][] dp = new int[n + 2][n + 2];
9 for (int len = 2; len <= n + 1; len++) {
10 for (int left = 0; left + len <= n + 1; left++) {
11 int right = left + len;
12 int best = 0;
13 for (int k = left + 1; k < right; k++) {
14 int coins = dp[left][k] + dp[k][right] + a[left] * a[k] * a[right];
15 if (coins > best) best = coins;
16 }
17 dp[left][right] = best;
18 }
19 }
20 return dp[0][n + 1];
21 }
22}