The trap in this problem is thinking forward: “which balloon do I burst first?” makes the reward for bursting balloon i depend on whichever neighbors haven’t been burst yet, which changes unpredictably as the game proceeds. The fix is to think about the last balloon burst in a range instead of the first. If balloon k is the last one burst within the open interval (left, right), then at the moment it is burst, its neighbors are guaranteed to still be exactly nums[left] and nums[right] — everything strictly between them is already gone. That reframing removes the “who are my current neighbors” ambiguity and makes the subproblems independent, which is exactly what DP needs.
Brute Force Recursion (Choose Last Balloon Per Interval)
Time O(2^n)Space O(n)Pad nums with a virtual 1 on each side so boundary balloons are handled uniformly. For an open interval (left, right) of balloon indices still in play, try every choice of k as the last balloon burst in that interval: bursting it earns nums[left] * nums[k] * nums[right] (since by the time it’s last, its only remaining neighbors are the interval’s edges), plus whatever the two sub-intervals (left, k) and (k, right) can independently yield.
class Solution: def maxCoins(self, nums: list[int]) -> int: balloons = [1] + nums + [1] n = len(balloons) def rec(left: int, right: int) -> int: if left + 1 == right: return 0 best = 0 for k in range(left + 1, right): coins = balloons[left] * balloons[k] * balloons[right] coins += rec(left, k) + rec(k, right) best = max(best, coins) return best return rec(0, n - 1)Without caching, the same (left, right) interval is recomputed every time it’s reached through a different split — exponential blow-up over overlapping intervals.
2-D Interval DP Table (Bottom-Up)
OptimalTime O(n^3)Space O(n^2)Memoize by interval: dp[left][right] is the maximum coins obtainable from bursting every balloon strictly between indices left and right in the padded array (with left and right themselves never burst — they act as fixed boundary markers for the interval). Build up from the smallest intervals to the full array — adjacent pairs (right - left = 1) form a base band worth 0 coins, the loop’s first real cells have right - left = 2 (exactly one balloon between the boundaries), and every larger interval depends only on strictly smaller intervals nested inside it.
class Solution: def maxCoins(self, nums: list[int]) -> int: balloons = [1] + nums + [1] n = len(balloons) dp = [[0] * n for _ in range(n)] for length in range(2, n): # interval width, smallest first for left in range(n - length): right = left + length best = 0 for k in range(left + 1, right): coins = balloons[left] * balloons[k] * balloons[right] coins += dp[left][k] + dp[k][right] best = max(best, coins) dp[left][right] = best return dp[0][n - 1]Each cell needs all smaller intervals nested strictly inside it — not just its immediate row/column neighbors — so the interesting action is the per-interval decision: which balloon to leave for last. The trace below replays that decision for nums = [3, 1, 5, 8] (padded to [1, 3, 1, 5, 8, 1]): the indigo k chip in the strip is the last balloon popped inside the current interval (l, r), the chips in the comparison row score every candidate k, and emerald cells mark intervals already solved. Watch step 6 (interval (0, 3)) — that is the first interval with an actual choice, where the recurrence first assembles a result from two already-solved sub-intervals:
Padded balloons
The table holds every interval of the padded array [1, 3, 1, 5, 8, 1]: dp[l][r] is the best score for bursting all balloons strictly between l and r. The base band r = l + 1 has no balloon between its boundaries, so it stays 0. Every fill above it reuses only smaller intervals already on the table.
Two take-aways. First, the base band r = l + 1 — cells with no balloon between the boundaries — contributes 0, and every real interval fills upward in order of width r - l, reusing only strictly smaller intervals already on the table. Second, the winning k is not bookkeeping: it is the actual balloon popped last. Reading the winners backward — (0, 5) leaves 8 last, (0, 4) leaves 3 last, (1, 4) leaves 5 last, (1, 3) leaves 1 last — recovers the statement’s optimal burst order, values 1, 5, 3, 8, scoring 3·1·5 = 15, then 3·5·8 = 120, then 1·3·8 = 24, then 1·8·1 = 8, for 15 + 120 + 24 + 8 = 167. Every optimal order ends with the 8.
Complexity: there are O(n^2) intervals (left, right), and each considers O(n) split points k → O(n^3) time. The dp table itself is O(n^2) space.