Burst Balloons
You have a row of balloons with numbers on them. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where the boundaries count as 1, and the remaining balloons close ranks. Find the maximum coins obtainable by bursting all balloons in some order.
- 1 ≤ n ≤ 300
- 0 ≤ nums[i] ≤ 100
- Bursting first makes neighbours shift — think about which balloon is burst last in a range
- Fix the last balloon in (l, r): its neighbours are l and r, fixed
- Interval DP over ranges
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Pad the array with 1 at both ends. Let best[l][r] be the maximum coins from bursting every balloon strictly between l and r. Choose the balloon k burst last in that range: its neighbours at that moment are exactly l and r, so best[l][r] = max over k of best[l][k] + nums[l]·nums[k]·nums[r] + best[k][r]. Fill by increasing range length and return best[0][n+1].
- Thinking about the first balloon to burst leads nowhere because the subproblems interact. Brute force over orders is O(n!).