Burst Balloons

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.