DP — Burst Balloons

solve(nums) — you have balloons numbered with nums. Bursting balloon i earns
left * nums[i] * right coins, where left and right are its current
neighbours (a missing neighbour counts as 1). Burst all balloons in the best order
and return the maximum coins.

The key reversal: instead of choosing the first balloon to burst, choose the
last one in an interval. When balloon k is the last one left between left
and right, its neighbours are exactly those boundaries, and the two sides are
independent subproblems. This is interval DP.

Examples

solve([3,1,5,8])  → 167
solve([1,5])      → 10
solve([7])        → 7
solve([])         → 0