#312 Burst Balloons
the problem
In plain words
Balloons have numbers nums[i]. Bursting balloon i earns nums[left] · nums[i] · nums[right], where left/right are its current neighbours (missing neighbours count as 1). Burst all of them; return the maximum total coins.
in nums = [3,1,5,8]
out 167
Burst 1, 5, 3, 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 167.
in nums = [1,5]
out 10
- 1 ≤ n ≤ 300
- 0 ≤ nums[i] ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval DP
Choosing the FIRST balloon to burst makes neighbours change unpredictably. Choose the LAST balloon k in an interval instead: when it bursts, its neighbours are the interval's fixed walls, and the two sides are independent subproblems.
solutions
From brute force to optimal
best(lo, hi) = max over k of v[lo]·v[k]·v[hi] + best(lo, k) + best(k, hi), with 1s padded on both ends.
- Pad nums with 1 on each side.
- Try every k strictly between the walls.
T(n) = 2·ΣT(k) solves to about 3ⁿ calls.
Recursion depth.
class Solution { public int maxCoins(int[] nums) { int[] v = new int[nums.length + 2]; // pad with a 1 on each side: edges always have neighbours v[0] = v[v.length - 1] = 1; System.arraycopy(nums, 0, v, 1, nums.length); return best(v, 0, v.length - 1); } /** Best coins from bursting every balloon strictly between walls lo and hi. */ private int best(int[] v, int lo, int hi) { int result = 0; for (int k = lo + 1; k < hi; k++) { // k is the LAST balloon popped in (lo, hi): its neighbours are then lo and hi int coins = v[lo] * v[k] * v[hi] + best(v, lo, k) + best(v, k, hi); result = Math.max(result, coins); } return result; }}Only (n + 2)² intervals exist.
- memo[lo][hi], −1 = unknown.
n² intervals × O(n) choices of k.
The memo.
class Solution { public int maxCoins(int[] nums) { int[] v = new int[nums.length + 2]; v[0] = v[v.length - 1] = 1; System.arraycopy(nums, 0, v, 1, nums.length); int[][] memo = new int[v.length][v.length]; for (int[] row : memo) java.util.Arrays.fill(row, -1); // -1 = not computed (coins are never negative) return best(v, 0, v.length - 1, memo); } private int best(int[] v, int lo, int hi, int[][] memo) { if (memo[lo][hi] != -1) return memo[lo][hi]; int result = 0; for (int k = lo + 1; k < hi; k++) { result = Math.max(result, v[lo] * v[k] * v[hi] + best(v, lo, k, memo) + best(v, k, hi, memo)); } return memo[lo][hi] = result; }}Fill dp[lo][hi] for gaps 2, 3, …, n + 1 so both halves are ready.
- For gap = 2..n+1, for lo: hi = lo + gap.
- dp[lo][hi] = max over k of dp[lo][k] + v[lo]·v[k]·v[hi] + dp[k][hi].
≈ n³/6 inner steps — about 4.5·10⁶ for n = 300.
The table; every interval may be read later.
class Solution { public int maxCoins(int[] nums) { int n = nums.length + 2; int[] v = new int[n]; v[0] = v[n - 1] = 1; System.arraycopy(nums, 0, v, 1, nums.length); int[][] dp = new int[n][n]; // dp[lo][hi] = best coins strictly between lo and hi for (int gap = 2; gap < n; gap++) { // short intervals before long ones for (int lo = 0; lo + gap < n; lo++) { int hi = lo + gap; for (int k = lo + 1; k < hi; k++) { // k = last balloon popped inside dp[lo][hi] = Math.max(dp[lo][hi], dp[lo][k] + v[lo] * v[k] * v[hi] + dp[k][hi]); } } } return dp[0][n - 1]; }}in the room
How to say it in the interview
talk track
- Say why "first burst" fails: after one burst, the left and right parts are no longer independent.
- Then: "pick the last balloon in (lo, hi); its neighbours are lo and hi, and the halves are independent".
traps
- Iterating lo upward with fixed hi — inner intervals aren't ready. Iterate by gap length.
- Forgetting the padding 1s at both ends.
what they ask next
Follow-ups
Other "last action" interval DPs?
Minimum Cost to Cut a Stick (LC 1547), Matrix Chain Multiplication, Minimum Score Triangulation (LC 1039) — same O(n³) shape.
before you submit
Edge cases to test
- One balloon → 1 · x · 1 = x.
- A 0 balloon earns nothing and zeroes every product it is part of while it stands — the DP handles it with no special case.
- Bursting the biggest first is not optimal: [3,1,5,8] → 167.
practise next
Similar problems
- #5Longest Palindromic SubstringMediumin Dynamic Programming
- #416Partition Equal Subset SumMediumin Dynamic Programming