Burst Balloons
Problem
Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbours (out-of-range neighbours count as 1). Burst every balloon in the best order and return the maximum coins.
Example 1
Input: [3, 1, 5, 8] Output: 167
Burst 1, 5, 3, 8: 15 + 120 + 24 + 8.
Test cases
Case 1
Input: [3,1,5,8] Expected: 167
Case 2
Input: [1,5] Expected: 10
Case 3
Input: [7] Expected: 7
View solutionHide solution1 approach
1. Interval DP on the last balloon burst
Time O(n³)Space O(n²)
Pad with 1s. dp[l][r] = best coins bursting everything strictly between l and r. Choosing k as the LAST to burst in (l, r) makes its neighbours exactly l and r, so the two sides are independent.
function maxCoins(nums) { const a = [1, ...nums, 1], n = a.length; const dp = Array.from({ length: n }, () => new Array(n).fill(0)); for (let len = 2; len < n; len++) { for (let l = 0; l + len < n; l++) { const r = l + len; for (let k = l + 1; k < r; k++) dp[l][r] = Math.max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]); } } return dp[0][n - 1];}Thinking "first to burst" fails because neighbours change — "last to burst" is the key insight.