DSA problem
Burst Balloons
You are given n balloons with values nums. If you burst balloon i you collect nums[i - 1] * nums[i] * nums[i + 1] coins, where indices outside the array act as 1. After bursting, the remaining balloons become neighbors, and the indexing shifts accordingly. Return the maximum coins you can collect by bursting all balloons wisely.
A natural but wrong approach is to think top-down: "which balloon should I burst first?" The trouble is that when you burst a balloon early, its neighbors close in, and which neighbors you end up with depends on the entire later sequence — the state space explodes. The right insight is to flip the question: "which balloon should I burst last in this range?"
Pad nums with sentinel 1s at both ends: arr = [1] + nums + [1]. Consider an inclusive range (i, j) (exclusive of both endpoints, which are sentinels for that subproblem). Let dp[i][j] be the max coins obtainable by bursting every balloon strictly between i and j. If k is the last balloon burst in that range, then at the moment of bursting, its neighbors are precisely arr[i] and arr[j], giving arr[i] * arr[k] * arr[j] coins. The other balloons split into two independent subproblems dp[i][k] and dp[k][j].
So dp[i][j] = max over k in (i, j) of (dp[i][k] + arr[i] * arr[k] * arr[j] + dp[k][j]). Fill dp by ascending range length. The final answer is dp[0][n + 1]. Time O(n^3), space O(n^2).
Examples
nums = [3,1,5,8]167nums = [1,5]10nums = [9]9Constraints
- n == nums.length
- 1 <= n <= 300
- 0 <= nums[i] <= 100
- Indices outside the array contribute 1 when computing the burst score.
- You must burst every balloon exactly once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.