Burst Balloons

The problem

You are given nums, the numbers on a row of balloons. Burst the balloons one at a time, in any order, until none is left. Bursting a balloon earns its number times the number on its left neighbor times the number on its right neighbor, and a missing neighbor counts as 1. After a burst, the balloons on the two sides of the hole become neighbors. Return the largest total of coins you can earn. A balloon may show 0.

What to write

function solve(nums: number[]): number

Input
nums = [3,1,5,8]

Output
167

Input
nums = [1,5]

Output
10

Constraints

nums contains nonnegative integers and has at most 300 entries.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   With up to 300 balloons, trying every order is impossible: 10 balloons already have 3,628,800 orders. But 300 is small enough to do some work for every choice of three balloons, about 4.5 million choices. Notice what makes this hard: every burst changes which balloons are neighbors.

2. Hint 2: Ask a smaller question

   Take the row 3, 1, 5. For each of its six orders, write down what the very last burst earns. Compare the orders that leave the same balloon for last. What stood next to that balloon at the end, and did the earlier bursts change that?

3. Hint 3: Name the pattern

   The balloon that is burst last between two others stands until both of its sides are empty. So its left side and its right side never touch and can be solved separately, as two shorter stretches. An answer for every stretch, or interval, of the row, built from the answers for shorter ones, is interval dynamic programming. Read the lesson on interval dynamic programming.

4. Hint 4: State the invariant

   Pick two balloons as ends and keep them standing. Their cell holds the most coins from bursting every balloon between them. A balloon burst last there earns its number times the two ends, plus the cell for the left end and that balloon, plus the cell for that balloon and the right end. The cell is the best such total.

5. Hint 5: Sketch the pseudocode

   Put a 1 before and after the row. best = 0 for every pair. For width from 2 up, for every left with right = left + width inside the row, for every k between them: best[left][right] = the larger of itself and best[left][k] + best[k][right] + value[left] × value[k] × value[right]. Return best for the two added 1s.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Choose which balloon is last inside an interval. Its surviving neighbors are fixed interval boundaries, so the two smaller intervals are independent.

The slow way

Try every order of bursting and keep the best total. It is correct, but the orders multiply too fast: 4 balloons have 24 orders, 10 have 3,628,800, and the row may hold 300. Shortcuts that look sensible fail as well. Always bursting the smallest balloon earns 78 on example 1, and always taking the biggest burst available earns at most 96. The best is 167.

The insight

Asking which balloon goes first leads nowhere: its two sides merge and keep affecting each other. Ask which one goes last instead. Take the balloons between two that stay standing, a stretch called an interval. The one burst last there stands the whole time, so its left side never meets its right side, and at its own burst its neighbors are exactly the two standing balloons.

Step by step

1. Add a 1 at each end to stand for the missing outside neighbors. A missing neighbor counts as 1. With a real 1 on each side, the first and the last balloon have two neighbors like every other balloon, and no special case is needed. The two added 1s are never burst.
2. Make a table: the most coins from bursting all between two ends. A cell belongs to two positions of the row, called its ends. It holds the most coins you can earn by bursting every balloon between the ends while both ends stay. With nothing between them the cell stays 0.
3. Go through every pair of ends, the closest pairs first. A cell is built from cells whose ends are closer together. Taking the closest pairs first means those cells are already final when they are read.
4. Try each balloon between the ends as the last one burst there. Some balloon between the ends must be the last to go. Which one is best is not known in advance, so every one of them gets a turn.
5. Burst last, its neighbors are the two ends: multiply the three. By then every other balloon between the ends is gone, and the ends themselves still stand. So the coins for this burst are fixed: left end times this balloon times right end.
6. Add the best coins of the part on each side and keep the largest. Everything left of this balloon and everything right of it went earlier, and this balloon kept the two parts apart. Their best totals are in two cells: left end with this balloon, and this balloon with right end.
7. Return the cell whose ends are the two added 1s. Every real balloon lies between the two added 1s, so that cell is the most coins from bursting the whole row. Its ends are the farthest apart, so it is filled last.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Add a 1 at each end to stand for the missing outside neighbors
  const a = [1, ...nums, 1];
  const n = a.length;
  // 2. Make a table: the most coins from bursting all between two ends
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  // 3. Go through every pair of ends, the closest pairs first
  for (let width = 2; width < n; width++) {
    for (let l = 0; l + width < n; l++) {
      const r = l + width;
      // 4. Try each balloon between the ends as the last one burst there
      for (let k = l + 1; k < r; k++) {
        // 5. Burst last, its neighbors are the two ends: multiply the three
        const coins = a[l] * a[k] * a[r];
        // 6. Add the best coins of the part on each side and keep the largest
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + coins);
      }
    }
  }
  // 7. Return the cell whose ends are the two added 1s
  return dp[0][n - 1];
}

function solve(nums: number[]): number {
  // 1. Add a 1 at each end to stand for the missing outside neighbors
  const a = [1, ...nums, 1];
  const n = a.length;
  // 2. Make a table: the most coins from bursting all between two ends
  const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  // 3. Go through every pair of ends, the closest pairs first
  for (let width = 2; width < n; width++) {
    for (let l = 0; l + width < n; l++) {
      const r = l + width;
      // 4. Try each balloon between the ends as the last one burst there
      for (let k = l + 1; k < r; k++) {
        // 5. Burst last, its neighbors are the two ends: multiply the three
        const coins = a[l] * a[k] * a[r];
        // 6. Add the best coins of the part on each side and keep the largest
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + coins);
      }
    }
  }
  // 7. Return the cell whose ends are the two added 1s
  return dp[0][n - 1];
}

def solve(nums):
    # 1. Add a 1 at each end to stand for the missing outside neighbors
    padded = [1, *nums, 1]
    n = len(padded)
    # 2. Make a table: the most coins from bursting all between two ends
    dp = [[0] * n for _ in range(n)]
    # 3. Go through every pair of ends, the closest pairs first
    for width in range(2, n):
        for left in range(n - width):
            right = left + width
            # 4. Try each balloon between the ends as the last one burst there
            for k in range(left + 1, right):
                # 5. Burst last, its neighbors are the two ends: multiply the three
                coins = padded[left] * padded[k] * padded[right]
                # 6. Add the best coins of the part on each side and keep the largest
                dp[left][right] = max(
                    dp[left][right], dp[left][k] + dp[k][right] + coins
                )
    # 7. Return the cell whose ends are the two added 1s
    return dp[0][n - 1]

Example 1, traced

Input
nums = [3,1,5,8]

Output
167

Why it works

Whatever the best order for the balloons between two ends is, one of them goes last. At that moment it earns its number times the two ends. Before that, its left part and its right part were cleared without touching each other, each as well as possible. Trying every candidate for the last balloon therefore finds the best total, and the closer pairs it needs are filled first.

Time and space

Time O(n³), extra space O(n²). Call the number of balloons n. There are about n² / 2 pairs of ends, and each pair tries up to n balloons as the last one: O(n³) time. With 300 balloons that is 4,545,100 tries. The table has (n + 2) × (n + 2) cells: O(n²) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Multiply the last balloon by the two ends, not by the balloons beside it in the original row. Those are already burst by then. With the original neighbors, example 1 gives 98 instead of 167.
• Fill the closest pairs first. Going through the table row by row from the top reads cells of lower rows that are still 0, and example 1 gives 63 instead of 167.
• Do not split on the balloon you burst first. Its two sides become neighbors and no longer count separately. Treating them as separate rows gives 66 on example 1 instead of 167.

Pattern

Interval dynamic programming. Builds on Coin Change and Edit Distance.

Keep going