DSA Tracker

Visualize

Burst Balloons

Interval DP on the LAST balloon burst, not the first

time O(n^3)space O(n^2)

Asking which balloon to burst FIRST goes nowhere: it splits the row into two halves that are no longer independent, because the balloons either side of the gap become neighbours. Asking which one bursts LAST fixes that. If k is last inside the open range (l, r), then everything left of k is gone before k pops and everything right of k is gone too, so the two halves never interact — and when k finally bursts, its neighbours are exactly l and r, which are still standing. That makes the score l*k*r independent of how the halves were played, so dp[l][r] = max over k of dp[l][k] + dp[k][r] + A[l]*A[k]*A[r]. Padding both ends with a 1 removes the edge cases.

Details

Animated on: nums=[3,1,5,8] — burst every balloon; bursting i pays nums[left]*nums[i]*nums[right] with the CURRENT neighbours. Maximise the total.

Problem:Burst BalloonsHard

Interval DP on the LAST balloon burst, not the first

step 1 / 15

dp[l][r] — most coins obtainable from the balloons strictly between padded positions l and r

Pad the row with a 1 at each end so every real balloon has a neighbour: [1, 3, 1, 5, 8, 1]. dp[l][r] means "best coins from bursting only what lies BETWEEN l and r". The 0s are ranges with nothing inside them.

Pseudocode
1FUNCTION maxCoins(nums)
2  A <- [1] + nums + [1]
3  n <- LENGTH(A)
4  dp <- n x n table of 0
5  FOR gap FROM 2 TO n-1
6    FOR l FROM 0 TO n-1-gap
7      r <- l + gap
8      FOR k FROM l+1 TO r-1
9        dp[l][r] <- MAX(dp[l][r], dp[l][k] + dp[k][r] + A[l] * A[k] * A[r])
10  RETURN dp[0][n-1]

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Pad the row with a 1 at each end so every real balloon has a neighbour: [1, 3, 1, 5, 8, 1]. dp[l][r] means "best coins from bursting only what lies BETWEEN l and r". The 0s are ranges with nothing inside them.
  2. dp[0][2]: only balloon 3 lies between them, so it must burst last — its neighbours are still 1 and 1, giving 1*3*1 = 3.
  3. dp[1][3]: only balloon 1 lies between them, so it must burst last — its neighbours are still 3 and 5, giving 3*1*5 = 15.
  4. dp[2][4]: only balloon 5 lies between them, so it must burst last — its neighbours are still 1 and 8, giving 1*5*8 = 40.
  5. dp[3][5]: only balloon 8 lies between them, so it must burst last — its neighbours are still 5 and 1, giving 5*8*1 = 40.
  6. dp[0][3] = 30: burst 3 last (tried 3→30, 1→8). Choosing the LAST balloon is what makes the two halves independent — neither can ever touch the other, so both are just smaller dp cells.
  7. dp[1][4] = 135: burst 5 last (tried 1→64, 5→135). Choosing the LAST balloon is what makes the two halves independent — neither can ever touch the other, so both are just smaller dp cells.
  8. dp[2][5] = 48: burst 8 last (tried 5→45, 8→48). Choosing the LAST balloon is what makes the two halves independent — neither can ever touch the other, so both are just smaller dp cells.
  9. dp[0][4] = 159: burst 3 last (tried 3→159, 1→51, 5→70). Choosing the LAST balloon is what makes the two halves independent — neither can ever touch the other, so both are just smaller dp cells.
  10. dp[1][5] = 159: burst 8 last (tried 1→51, 5→70, 8→159). Choosing the LAST balloon is what makes the two halves independent — neither can ever touch the other, so both are just smaller dp cells.
  11. Answer cell, candidate 1 of 4: if balloon 3 bursts LAST, everything left of it (dp[0][1]=0) and right of it (dp[1][5]=159) is already solved, then 3 pops between the two padding 1s for 3 — 162 total. Best so far 162.
  12. Answer cell, candidate 2 of 4: if balloon 1 bursts LAST, everything left of it (dp[0][2]=3) and right of it (dp[2][5]=48) is already solved, then 1 pops between the two padding 1s for 1 — 52 total. Best so far 162.
  13. Answer cell, candidate 3 of 4: if balloon 5 bursts LAST, everything left of it (dp[0][3]=30) and right of it (dp[3][5]=40) is already solved, then 5 pops between the two padding 1s for 5 — 75 total. Best so far 162.
  14. Answer cell, candidate 4 of 4: if balloon 8 bursts LAST, everything left of it (dp[0][4]=159) and right of it (dp[4][5]=0) is already solved, then 8 pops between the two padding 1s for 8 — 167 total. Best so far 167.
  15. dp[0][5] = 167 — the whole row bursts between the two padding 1s, so this cell is the answer. Every cell under it was reused, never recomputed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Burst Balloons in the editorAll Dynamic Programming problemsBack to roadmap