Bursting balloon i earns nums[i−1]·nums[i]·nums[i+1] coins (out-of-range neighbors count as 1), after which its neighbors become adjacent. Return the maximum coins from bursting all balloons.
Fill dp[l][r] for open intervals in order of increasing width, so both halves of every split are already known.
1function maxCoins(nums: number[]): number {2const a = [1, ...nums, 1], n = a.length;3const dp = Array.from({ length: n }, () => new Array(n).fill(0));4for (let width = 2; width < n; width++)5for (let l = 0; l + width < n; l++) {6const r = l + width;7for (let k = l + 1; k < r; k++)8dp[l][r] = Math.max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]);9}10return dp[0][n - 1];11}
| 0:1 | 1:3 | 2:1 | 3:5 | 4:8 | 5:1 | |
|---|---|---|---|---|---|---|
| 0:1 | 0 | |||||
| 1:3 | 0 | |||||
| 2:1 | 0 | |||||
| 3:5 | 0 | |||||
| 4:8 | 0 | |||||
| 5:1 |
Adjacent pairs (l, l+1) contain no balloons: 0.
Space: play/pause · ←/→: step