LeetMotion
You are given an array nums of n integers, where each integer represents a balloon with that value. You must burst all the balloons.
If you burst balloon i, you gain nums[i-1] × nums[i] × nums[i+1] coins. If the left or right neighbor is out of bounds, treat it as 1.
Return the maximum coins you can collect by bursting all balloons in the optimal order.
1 ≤ n ≤ 3000 ≤ nums[i] ≤ 100The hard part: when you burst a balloon, its neighbors change. This makes "think forward" (which balloon should I burst first?) messy — the subproblems aren't independent.
i is the very last balloon left in [l, r], then at the moment of bursting it, its neighbors are fixed: nums[l-1] on the left and nums[r+1] on the right (the boundary balloons, which haven't been burst yet because they're outside this range).This transforms the problem into Interval DP:
dp[l][r] = max coins from bursting all balloons in range [l, r]i in [l, r]:i last = nums[l-1] × nums[i] × nums[r+1]dp[l][i-1] (best from left sub-range)dp[i+1][r] (best from right sub-range)i is already gone when i is burst, the two sub-ranges are independent — no interference.Pad the original array with 1s on both sides to avoid out-of-bounds checks at the boundaries. The answer is dp[1][n].
The naive approach: at each step, try every remaining balloon, pop it, compute coins based on current neighbors, and recurse on the resulting array. This is exponential — we rebuild and pass shrinking arrays at every level of recursion.
def maxCoins(nums: list[int]) -> int:
nums = [1] + nums + [1]
def dfs(nums):
if len(nums) == 2: # only boundary pads left
return 0
max_coins = 0
for i in range(1, len(nums) - 1):
coins = nums[i - 1] * nums[i] * nums[i + 1]
coins += dfs(nums[:i] + nums[i + 1:]) # remove balloon i
max_coins = max(max_coins, coins)
return max_coins
return dfs(nums)Time: O(n · 2^n) — the array shrinks by 1 each call but there are n! orderings. Space: O(n · 2^n) for the call stack plus array copies.
Instead of passing the shrinking array, pass indices (l, r) that define the subrange. Think in reverse: choose i as the last balloon burst in [l, r]. Since i is burst last, everything else in [l, r] is already gone, so the neighbors of i are the fixed boundary values nums[l-1] and nums[r+1].
(l, r) — the range boundaries. There are O(n²) unique ranges, and each range tries O(n) candidates for the last balloon. Total: O(n³).def maxCoins(nums: list[int]) -> int:
nums = [1] + nums + [1]
dp = {}
def dfs(l, r):
if l > r:
return 0
if (l, r) in dp:
return dp[(l, r)]
dp[(l, r)] = 0
for i in range(l, r + 1):
# i is the LAST balloon burst in [l, r]
coins = nums[l - 1] * nums[i] * nums[r + 1]
coins += dfs(l, i - 1) + dfs(i + 1, r)
dp[(l, r)] = max(dp[(l, r)], coins)
return dp[(l, r)]
return dfs(1, len(nums) - 2)Translate the memoization into an iterative table. We fill intervals from smallest to largest: single-element intervals first, then two-element, and so on. When we compute dp[l][r], all smaller sub-intervals dp[l][i-1] and dp[i+1][r] are already computed.
new_nums = [1] + nums + [1], n = len(nums).dp[n+2][n+2], all zeros.l from n down to 1 (smaller intervals computed first).r from l to n.i in [l, r]: dp[l][r] = max(dp[l][r], new_nums[l-1] * new_nums[i] * new_nums[r+1] + dp[l][i-1] + dp[i+1][r]).dp[1][n].def maxCoins(nums: list[int]) -> int:
n = len(nums)
new_nums = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for l in range(n, 0, -1): # smaller intervals first
for r in range(l, n + 1):
for i in range(l, r + 1): # i is the last balloon burst
coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
coins += dp[l][i - 1] + dp[i + 1][r]
dp[l][r] = max(dp[l][r], coins)
return dp[1][n]new_nums = [1, 3, 1, 5, 8, 1], indices 1–4 represent the original balloons. The table below shows dp[l][r] for all valid ranges:
| l＼r | r=1 (val=3) | r=2 (val=1) | r=3 (val=5) | r=4 (val=8) |
|---|---|---|---|---|
| l=1 (val=3) | 3 | 30 | 159 | 167 |
| l=2 (val=1) | – | 15 | 135 | 159 |
| l=3 (val=5) | – | – | 40 | 48 |
| l=4 (val=8) | – | – | – | 8 |
dp[1][4] = 167 is the answer — the maximum coins from bursting all 4 balloons.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force | O(n · 2^n) | O(n · 2^n) | Array copying + exponential branches |
| Top-Down DP | O(n³) | O(n²) | O(n²) unique states, O(n) work each |
| Bottom-Up DP | O(n³) | O(n²) | No recursion overhead, cache-friendly iteration |
If you choose first burst, the remaining array's structure changes unpredictably — the subproblems are not independent. Choosing the last burst in a range fixes the neighbors and makes subproblems cleanly separable.
# WRONG mental model: burst i first — neighbors shift coins = nums[i-1] * nums[i] * nums[i+1] # wrong — neighbors change after burst # CORRECT: burst i LAST in range [l, r] — neighbors are fixed boundary values coins = nums[l-1] * nums[i] * nums[r+1]
The problem says out-of-bounds neighbors are treated as 1. Pad the array explicitly: new_nums = [1] + nums + [1]. Without padding you need to handle edge cases everywhere in the inner loop, and it's easy to get them wrong.
Smaller intervals must be computed before larger ones. Iterate l from n down to 1 and r from l to n. This ensuresdp[l][i-1] and dp[i+1][r] are already filled when you compute dp[l][r].
[7] → 7 (single balloon, padded: 1×7×1)[1, 5] → 10 (burst 1 first: 1+5=6? No — 1×1×5 + 1×5×1 = 5+5=10 or 1×5×1 + 1×1×1 = 5+1=6. Best is 10.)[3, 1, 5, 8] → 167[4, 2, 3, 7] → 143
Discussion
…