TL;DR
Interval DP on padded balloons where k is the last balloon burst in each open interval — O(n³) time, O(n²) space.
Approach 1 — Brute force recursion
Pick each balloon to burst first, remove it, and recurse on the shortened row.
from typing import List
def maxCoins(nums: List[int]) -> int:
def best(balloons: List[int]) -> int:
if not balloons:
return 0
top = 0
for i in range(len(balloons)):
left = balloons[i - 1] if i > 0 else 1
right = balloons[i + 1] if i + 1 < len(balloons) else 1
gain = left * balloons[i] * right
rest = balloons[:i] + balloons[i + 1:]
top = max(top, gain + best(rest))
return top
return best(nums)
Complexity: roughly O(n · n!) time. Every ordering of bursts is explored, and the reformed rows do not line up into reusable subproblems. This is impractical beyond about 10 balloons, while the constraints allow up to 300.
Approach 2 — Reframe with “last to burst”, then memoize top-down
Bursting first is hard because it splits the row into two halves whose new boundaries depend on the deleted balloon, so the halves are not independent. Instead, let k be the last balloon burst in the open interval (left, right). When k pops, everything else inside is already gone, so its neighbors are exactly the fixed boundaries left and right, earning vals[left]*vals[k]*vals[right]. The two sub-intervals (left, k) and (k, right) are solved independently and share clean, fixed boundaries.
flowchart TD
A["burst(left, right)"] --> B["pick k = last balloon burst inside"]
B --> C["burst(left, k)"]
B --> D["vals[left] * vals[k] * vals[right]"]
B --> E["burst(k, right)"]
State / recurrence. Pad to vals = [1] + nums + [1]. burst(left, right) = max coins obtainable from all balloons strictly inside the open interval (left, right):
burst(left, right) = max over k in (left+1 .. right-1) of
vals[left]*vals[k]*vals[right] + burst(left, k) + burst(k, right)
Base case: an interval with no interior balloon (right - left < 2) yields 0.
from typing import List
from functools import lru_cache
def maxCoins(nums: List[int]) -> int:
vals = [1] + nums + [1]
@lru_cache(maxsize=None)
def burst(left: int, right: int) -> int:
if right - left < 2:
return 0
best = 0
for k in range(left + 1, right):
coins = vals[left] * vals[k] * vals[right]
coins += burst(left, k) + burst(k, right)
best = max(best, coins)
return best
return burst(0, len(vals) - 1)
Complexity: O(n³) time (O(n²) intervals × O(n) choices of k), O(n²) space.
Approach 3 — Bottom-up interval tabulation (the 2-D table)
The same recurrence, filled iteratively by increasing interval width so both sub-intervals dp[left][k] and dp[k][right] are already computed when they are needed.
State / recurrence. dp[left][right] = max coins from bursting all balloons strictly between indices left and right in the padded array. Same transition as Approach 2. We iterate the gap right - left from 2 upward.
from typing import List
def maxCoins(nums: List[int]) -> int:
vals = [1] + nums + [1]
n = len(vals)
dp = [[0] * n for _ in range(n)]
for gap in range(2, n): # distance from left to right boundary
for left in range(n - gap):
right = left + gap
best = 0
for k in range(left + 1, right):
coins = vals[left] * vals[k] * vals[right]
coins += dp[left][k] + dp[k][right]
best = max(best, coins)
dp[left][right] = best
return dp[0][n - 1]
Walkthrough with nums = [3,1,5,8], so vals = [1,3,1,5,8,1]. Width-2 intervals hold a single balloon: e.g. dp[0][2] (balloon 3) = 1·3·1 = 3; dp[1][3] (balloon 1) = 3·1·5 = 15. Wider intervals combine these. The final dp[0][5] chooses the last balloon to burst across the whole row; the optimum corresponds to bursting order 1, 5, 3, 8 and evaluates to 167.
Complexity: O(n³) time, O(n²) space.
Note on space optimization
Interval DP fills a full triangular table where dp[left][right] depends on entries in the same row to the right and the same column below, not on a single previous row. There is no rolling-row reduction here — the O(n²) table is inherent.
Common pitfalls
- Framing the split around the first balloon burst; the halves then share a moving boundary and the subproblems do not decompose cleanly. Always split on the last burst.
- Forgetting the padding
1s, which makes the edge balloons mishandle their boundary neighbors.
- Filling the table in the wrong order — you must go by increasing interval width so both sub-intervals are ready; a naive
for left / for right loop can read uncomputed cells.
- Treating
(left, right) as inclusive; here they are the boundaries and the interval of balloons to burst is strictly between them.
Pattern takeaway
When bursting/removing an element reshuffles adjacency, “which to remove first” tangles the subproblems — invert it to “which to remove last”, which freezes the boundaries and makes the two sides independent. That yields interval DP: dp[left][right] over a range with the split point ranging inside it, filled by increasing width. This last-operation-first framing also applies to matrix-chain multiplication and other divide-on-a-pivot problems.