Burst balloons

Hard TimeO(n³) SpaceO(n²)

Balloons in a row each carry a number. Bursting one earns the product of it and its two current neighbours, a missing neighbour off either end counting as 1, and those two neighbours then become adjacent. Every balloon is burst exactly once. Return the most coins obtainable by bursting them all.

Examples

Example 1

Input
nums = [3, 1, 5, 8]
Output
167
Burst 1, then 5, then 3, then 8: 15 + 120 + 24 + 8 = 167.

Example 2

Input
nums = [5]
Output
5
One balloon with both neighbours missing, so 1 × 5 × 1 = 5.

The Code

function maxCoins(nums) {
  const balloons = [1].concat(nums, [1]);
  const n = balloons.length;
  const dp = [];
  for (let i = 0; i < n; i++) {
    dp.push(new Array(n).fill(0));
  }
  for (let width = 2; width < n; width++) {
    for (let left = 0; left + width < n; left++) {
      const right = left + width;
      for (let last = left + 1; last < right; last++) {
        const coins = balloons[left] * balloons[last] * balloons[right] + dp[left][last] + dp[last][right];
        if (coins > dp[left][right]) dp[left][right] = coins;
      }
    }
  }
  return dp[0][n - 1];
}
maxCoins([3, 1, 5, 8]);
Done

The first 28 calls, of 57. This one does not fit on a page.

Step through maxCoins([3, 1, 5, 8]) call by call

More like this

All dynamic programming examples (20) →