269. Burst Balloons
A row of balloons hangs in front of you, and each one has a number painted on it, given as the integer array nums.
You must pop every balloon. Popping the balloon at position i pays you left × nums[i] × right coins, where left and right are the numbers on the nearest balloons still unpopped on each side of i. If there is no balloon left on a side, treat that side as the number 1.
The order you pop in changes how much you collect, because each pop makes two previously separated balloons adjacent. Given nums, return the maximum total coins you can collect by choosing the best popping order.
Example 1:
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation: Pop the 1 first (3·1·5 = 15), then the 5 (3·5·8 = 120), then the 3 (1·3·8 = 24), then the 8 (1·8·1 = 8). Total 15 + 120 + 24 + 8 = 167, which is the best possible.
Example 2:
Input: nums = [1, 5]
Output: 10
Explanation: Pop the 1 first for 1·1·5 = 5, then the 5 for 1·5·1 = 5. Total 10. Popping the 5 first only yields 1·5·1 + 1·1·1 = 6.
Constraints:
- 1 ≤ nums.length ≤ 300
- 0 ≤ nums[i] ≤ 100
Hints:
Thinking about which balloon to pop *first* is painful: the first pop changes every neighbor relationship after it. Flip the question — for a stretch of balloons, decide which one is popped *last*.
If balloon k is the last to go inside the open interval (l, r), its payout is fixed: a[l] · a[k] · a[r], because only the boundary balloons survive around it. The two sides (l, k) and (k, r) then become completely independent subproblems — that is interval DP.
Pad the array with a 1 on each end so the boundary math needs no special cases, then fill dp[l][r] for intervals of growing width.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 1, 5, 8]
Expected output: 167