Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbors (1 beyond the ends). Return the maximum coins from bursting all balloons.
Before you code
Choosing which balloon to burst first changes everyone's neighbors, which makes subproblems messy. Choosing which balloon bursts last in a range fixes its neighbors at the range's boundaries and splits the range in two independent halves.
Hints
- Pad the array with 1 at both ends.
dp[l][r]is the best for the balloons strictly between l and r.dp[l][r] = max over k of dp[l][k] + nums[l]*nums[k]*nums[r] + dp[k][r].- Fill by increasing
r - lso shorter intervals are ready first. O(n³).
Production & complexity notes
When solving Burst balloons on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Bottom-up tables to reinforce the underlying pattern.
What it practices
Choosing a fill order from the dependencies, from Bottom-up tables.