Burst Balloons: Reverse Interval DP

Given n balloons with values nums, bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins (the product of itself and its current neighbours). After it bursts, the neighbours become adjacent. Find the maximum coins you can collect by bursting all balloons. The naive simulation is hard because bursting changes neighbours — Reverse interval DP elegantly sidesteps this difficulty.

If we try to define dp[i][j] as maximum coins from bursting balloons in range [i, j] and think about which balloon to burst first, we face a problem: bursting balloon k first means nums[k-1] and nums[k+1] must be the current neighbours — but those balloons might be burst later, changing neighbours dynamically. The state is hard to define cleanly in the forward direction.

The trick is to think about which balloon is the last to burst in interval [i, j]. When balloon k is the last burst in [i, j], all other balloons in [i, j] are already gone. So balloon k's neighbours are exactly nums[i-1] and nums[j+1] — the boundary balloons just outside the interval. This makes the coin calculation for the last burst deterministic: it does not depend on the order of earlier bursts.

Add sentinel balloons: prepend and append 1 to nums to form nums = [1] + nums + [1]. Define dp[i][j] as the maximum coins from bursting all balloons strictly between indices i and j (exclusive), where nums[i] and nums[j] are the surviving boundary balloons. Recurrence: for each candidate last balloon k in (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

We pad the array with sentinels, initialise the DP table to zero (empty interval = 0 coins), and fill in increasing interval length. The final answer is dp[0][n+1], representing the maximum coins from bursting all original balloons with the sentinels as permanent boundaries.

For [3, 1, 5, 8], padded to [1, 3, 1, 5, 8, 1] (indices 0-5). We want dp[0][5]. For length=2 intervals (one balloon inside): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. Building up, the optimal is to burst 1 last among {3,1,5,8} after bursting neighbours first, giving 167 total coins.

There are O(n²) intervals and for each interval we try O(n) split points, giving O(n³) time complexity. Space is O(n²) for the DP table. For n = 500 balloons, this is 125 million operations — feasible for interview constraints. The sentinel padding simplifies boundary handling: without it, you'd need explicit checks for whether i-1 and j+1 are in bounds.

The same solution can be written top-down with @lru_cache, which may be more intuitive to derive during an interview. Define solve(i, j) as max coins in open interval (i, j). The function tries all k as the last burst and memoises results. Both approaches have identical time and space complexity.

A common mistake is defining dp[i][j] as coins when the first balloon in [i,j] is burst, not the last. This fails because the coin calculation for the first burst depends on neighbouring balloons that haven't been burst yet — and the state of those neighbours changes as the algorithm progresses. Always think about the last element in interval DP when boundaries depend on remaining elements.

Sentinels of value 1 are chosen because they act as neutral elements for multiplication. When a boundary balloon is the last to burst, its coin value is boundary * last * boundary = 1 * last * 1 = last. Using 0 would give 0 coins (wrong), and using other values would distort the computation. The sentinel trick cleanly unifies all boundary cases without special-casing the leftmost and rightmost balloons.

In standard interval DP (matrix chain), the split point k represents where we divide the problem into two sub-problems solved independently. In Burst Balloons, k is the last to burst in the interval, making the two sub-intervals [i,k] and [k,j] independent given that k is still present as a boundary. This reversed perspective is the creative insight that makes burst balloons solvable by interval DP.

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

In this lesson you learned: forward simulation fails because bursting balloons changes neighbours unpredictably, the reverse insight defines k as the last balloon burst in an interval, making neighbours nums[i] and nums[j], and the recurrence dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) with sentinel padding gives an O(n³) solution. Next up we shift to knapsack DP, starting with the classic 0/1 knapsack and its space optimisation.