Burst Balloons
Burst Balloons is a hard dynamic programming problem solved with the interval dp pattern.
The best approach, optimal (interval dp, last balloon to burst), runs in O(n³) time and O(n²) space.
Below are 2 approaches in Java, from try every burst order (recursion) up.
Problem
Balloons are painted with numbers nums. Bursting balloon i earns left · nums[i] · right, where left and right are its current neighbours (a missing neighbour counts as 1). After bursting, its neighbours become adjacent. Return the maximum coins from bursting all balloons.
Examples
Example 1
- Input
nums = [3, 1, 5, 8]- Output
167- Why
- Burst 1, 5, 3, 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 167.
Example 2
- Input
nums = [1, 5]- Output
10
Constraints
1 <= n <= 300;0 <= nums[i] <= 100.- Out-of-range neighbours count as 1.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Try every burst order (recursion) | O(n!) | O(n) |
| Optimal (interval DP, last balloon to burst) | O(n³) | O(n²) |
1Try every burst order (recursion)
O(n!)O(n)Remove each balloon in turn, add its coins with its current neighbours, and recurse on the remaining list.
- For each remaining index, burst it and recurse; take the max.
class Solution {
public int maxCoins(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int x : nums) list.add(x);
return best(list);
}
private int best(List<Integer> b) {
int res = 0;
for (int i = 0; i < b.size(); i++) {
int left = i > 0 ? b.get(i - 1) : 1, right = i + 1 < b.size() ? b.get(i + 1) : 1;
int v = b.remove(i);
res = Math.max(res, left * v * right + best(b));
b.add(i, v);
}
return res;
}
}2Optimal (interval DP, last balloon to burst)
O(n³)O(n²)Pad the array with 1 at both ends. dp[l][r] = best coins from bursting every balloon strictly between l and r. If k is the last one burst there, its neighbours are l and r: dp[l][r] = max over k of dp[l][k] + a[l]·a[k]·a[r] + dp[k][r].
- a = [1] + nums + [1].
- For gap = 2..n + 1, for l, r = l + gap: try every k in (l, r).
- Return dp[0][n + 1].
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] a = new int[n + 2];
a[0] = a[n + 1] = 1;
for (int i = 0; i < n; i++) a[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] + a[l] * a[k] * a[r] + dp[k][r]);
}
return dp[0][n + 1];
}
}Edge cases to test
- Zeros in nums
- Single balloon
Hints
Hint 1
Choosing which balloon to burst first leaves messy neighbours. Choose which one to burst LAST in the range (l, r): its neighbours are then exactly l and r.
FAQ
What is the best time complexity for Burst Balloons?
Optimal (interval DP, last balloon to burst) runs in O(n³) time and O(n²) extra space.
Which pattern does Burst Balloons use?
It is a dynamic programming problem that uses the interval dp pattern. Other problems with the same pattern: Matrix Chain Multiplication.
Is there a brute force solution for Burst Balloons?
Yes. Try every burst order (recursion) takes O(n!) time and O(n) space. Remove each balloon in turn, add its coins with its current neighbours, and recurse on the remaining list.
Which edge cases should I test for Burst Balloons?
Zeros in nums; Single balloon.