Burst Balloons

Problem

You are given n balloons in a row, each labelled with a number nums[i]. Bursting balloon i earns you nums[i-1] * nums[i] * nums[i+1] coins, after which the balloon disappears and its former neighbours become adjacent. Treat any missing neighbour beyond either end of the row as having value 1. Choose the bursting order that maximises the total coins, and return that total.

• Up to 250 balloons.
• Each balloon's number is between 0 and 120.

Examples

• nums = [4, 2, 6, 3] → 136. Burst 2 (426=48), then 6 (463=72), then 3 (431=12), then 4 (141=4); 48+72+12+4 = 136.
• nums = [2, 9] → 27. Bursting 9 first earns 191 + 121 = 11; bursting 2 first earns 129 + 191 = 27, so order matters.
• nums = [6] → 6. One balloon with implicit 1s on both sides.

Hints

1. Choosing which balloon to burst first makes the remaining balloons' neighbours depend on that choice, so the two sides do not separate. Try the opposite question.
2. If balloon k is the last one burst within the range (lo, hi), its neighbours at that moment are exactly lo and hi, whatever happened earlier.
3. Interval DP on the padded array: dp[lo][hi] = max over k of dp[lo][k] + nums[lo]*nums[k]*nums[hi] + dp[k][hi].