Burst balloons
HardChoose the balloon burst last
Problem
Burst balloons to maximize coins, where bursting balloon i gives left*i*right of its current neighbours.
Decide which balloon bursts LAST in each range; its neighbours are the fixed walls (interval DP).
The idea
Deciding which balloon to burst first makes the subproblems overlap awkwardly, because the neighbours change. Choosing which one bursts *last* in an interval keeps its two boundaries fixed, so the two sides become independent subproblems.
The trick
- Think last, not first — that is the entire insight.
- Pad with 1s at both ends so the boundaries always exist.
- O(n³).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [3,1,5,8] Values: 3, 1, 5, 8.
1pad with 1s2dp[i][j]=max over k of dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]Input
- array
- [3, 1, 5, 8]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 1, 5, 8]
- Output:
- 167
- Explanation:
- Bursting in the best order earns 167 coins.
Example 2
- Input:
- nums = [1, 5]
- Output:
- 10
- Explanation:
- Best order → 10.
Example 3
- Input:
- nums = [7]
- Output:
- 7
- Explanation:
- One balloon → 7.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.