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.