← DSA Atlas
Dedicated problem page · #312

Burst Balloons

HardTwo-Dimensional Dynamic ProgrammingInterval DP on last-to-burstInterval dynamic programming
Solve on LeetCode ↗
312
HardTwo-Dimensional Dynamic ProgrammingInterval dynamic programmingInterval DP on last-to-burst

Burst Balloons

You are given n balloons, each painted with a number in the array nums. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where out-of-range neighbors are treated as a balloon with value 1. After a balloon bursts, its neighbors become adjacent. Return the maximum coins you can collect by bursting all balloons in an optimal order.

Open official problem prompt ↗
In plain English

Find the maximum total coins from bursting every balloon, given that each burst's payout depends on whichever balloons are currently adjacent.

Picture it like this

Think of a fireworks finale: instead of planning which shell to fire first, you plan which shell fires LAST in each section of the sky. Once you fix the last shell, the sky splits into two independent sections you can plan separately.

Example
Input
nums = [3, 1, 5, 8]
Output
167
Why
Bursting in order 1,5,3,8 yields 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15+120+24+8 = 167.
Constraints
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Pattern lesson

See the pattern, then code

Interval DP on last-to-burst
Recognition clue

Bursting order matters and each choice reshapes the neighbors, so a greedy or left-to-right pass fails; you need to decide over sub-ranges, which signals interval DP.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Instead of asking which balloon to burst first, ask which balloon in an open interval (left, right) is burst LAST. That last balloon's neighbors are exactly the fixed boundaries left and right, so its coin value is deterministic and the sub-intervals become independent.

New words, made simpleKnow these before the algorithm
Interval DP
Dynamic programming where each state is a contiguous range [i, j] and answers are built from smaller ranges.
Sentinel
A dummy boundary value (here, 1) added so edge balloons always have a defined neighbor.
Last-to-burst
The reframing trick: choosing the final balloon in a range makes its neighbors fixed and the sub-ranges independent.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force all orders

Factorial blow-up; impossible beyond ~10 balloons.

Try every possible bursting permutation and take the max.

Time O(n!)Space O(n)
First-to-burst DP

Fails because after the first burst the range no longer splits into independent, boundary-fixed pieces.

Define dp on the balloon burst first in a range.

Time O(n^3)Space O(n^2)
Best choiceLast-to-burst interval DP

Correct and efficient because the last-burst choice keeps sub-intervals independent.

dp[left][right] picks the last balloon k in the open interval; its neighbors are the fixed boundaries left and right.

Time O(n^3)Space O(n^2)
The rule we keep true

Invariant

dp[left][right] always equals the maximum coins obtainable from bursting exactly the balloons strictly inside (left, right), with a[left] and a[right] still present as boundaries.

Why this is correct

Reasoning

In any order, some balloon is burst last within a range; at that moment only the range's two boundaries remain beside it, so its payout is fixed at a[left]*a[k]*a[right]. Everything burst before it lies entirely on one side or the other, giving two independent subproblems. Trying all k covers every possible last choice, so the max is optimal.

The algorithm in three movesSay these aloud before coding
1Pad nums with a 1 on each end so boundaries always exist

padded a = [1,3,1,5,8,1]

2Let dp[left][right] be the max coins from bursting all balloons strictly between indices left and right

dp[0][2] (just balloon 3) = 1*3*1 = 3

3For each interval, try every k as the last balloon burst: gain a[left]*a[k]*a[right] plus dp[left][k] and dp[k][right]

k=last: dp[0][5] combines sub-intervals + boundary product

4Iterate by increasing interval length so sub-intervals are solved first

5Return dp[0][n-1] over the padded array

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
12
53
84
15
1 · Readnums = [3,1,5,8]
2 · AskHow do we guarantee boundaries exist?
3 · Update statea = [1,3,1,5,8,1], dp all zero
4 · ResultSentinels added at indices 0 and 5
Key takeaway

The padded array with sentinel 1s at both ends serving as permanent boundaries for every interval.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Pad and allocate

    Wrap nums with sentinel 1s and create the (n x n) dp table over the padded indices.

  2. 2
    Lines 6-8Grow intervals

    Iterate interval length from 2 upward so every sub-interval is already computed before the enclosing one.

  3. 3
    Lines 9-14Try each last balloon

    For each k inside (left, right), combine the boundary product with the two independent sub-interval results and keep the maximum.

  4. 4
    Lines 15Answer

    dp over the whole padded range gives the global optimum.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single balloon: answer is nums[0]*1*1 = nums[0]
  • Balloons with value 0 contribute 0 to any product but still must be burst
  • All equal values still require full O(n^3) evaluation
!

Common beginner mistakes

  • Defining dp on the first balloon burst instead of the last, which breaks independence
  • Forgetting the sentinel 1s and mishandling edge neighbors
  • Using dp[left][k-1] instead of dp[left][k]; the interval is open, so k itself is a boundary of the sub-problems
Check your understanding

Why is it correct to reason about the LAST balloon burst rather than the first?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles