Burst Balloons
Hard Interval DP (last to burst)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbours (outside counts as 1). Return the maximum coins for bursting all balloons.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: burst all balloons for the most coins.
Why this works: choose the LAST balloon to burst in a range; at that moment its neighbours are the range walls, so the left and right sides are independent.
Example: [3, 1, 5, 8] → padded [1,3,1,5,8,1]
best order gives 167✦Hints open one at a time
↗Approach
Pad the array with 1 at both ends. dp[l][r] = best for balloons strictly between l and r = max over k of dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]. Fill by increasing interval length.
</>Solution (Java)
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length + 2;
int[] a = new int[n];
a[0] = a[n - 1] = 1;
for (int i = 0; i < nums.length; i++) a[i + 1] = nums[i];
int[][] dp = new int[n][n];
for (int len = 2; len < n; len++) {
for (int l = 0; l + len < n; l++) {
int r = l + len;
for (int k = l + 1; k < r; k++) { // k is burst last between l and r
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];
}
}!Common mistake
Thinking about which balloon goes first — that state is not independent.
- Time: O(n³).
- Space: O(n²).