312. Burst Balloons

At a Glance

Topic: dp-2d
Pattern: Interval DP (optimal subarray removal / matrix chain style)
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft, ByteDance
Frequency: High
LeetCode: 312

You have nums[k] balloons labeled 0..n-1. Bursting balloon k yields nums[left] * nums[k] * nums[right] where left/right are nearest living neighbors. Burst all balloons; maximize total coins.

Recognition Cues

Remove elements one-by-one with neighbor-dependent score — think interval, not left-to-right prefix DP
Classic interval DP: last balloon burst in range splits problem

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Greedy — fails (counterexamples abound).
Interval DP — coins[left][right] = max coins from open interval (left, right) excluding endpoints — O(n^3) time, O(n^2) space — optimal.

Optimal Solution

Go

func maxCoins(nums []int) int {
	n := len(nums)
	padded := make([]int, n+2)
	padded[0] = 1
	padded[n+1] = 1
	for index := 0; index < n; index++ {
		padded[index+1] = nums[index]
	}
	// coins[left][right] = best score bursting all balloons strictly between left and right
	coins := make([][]int, n+2)
	for left := range coins {
		coins[left] = make([]int, n+2)
	}
	for width := 1; width <= n; width++ {
		for left := 1; left+width-1 <= n; left++ {
			right := left + width - 1
			best := 0
			for last := left; last <= right; last++ {
				gain := padded[left-1] * padded[last] * padded[right+1]
				gain += coins[left][last-1] + coins[last+1][right]
				if gain > best {
					best = gain
				}
			}
			coins[left][right] = best
		}
	}
	return coins[1][n]
}

JavaScript

function maxCoins(nums) {
  const n = nums.length;
  const padded = new Array(n + 2);
  padded[0] = 1;
  padded[n + 1] = 1;
  for (let index = 0; index < n; index += 1) {
    padded[index + 1] = nums[index];
  }
  const coins = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );
  for (let width = 1; width <= n; width += 1) {
    for (let left = 1; left + width - 1 <= n; left += 1) {
      const right = left + width - 1;
      let best = 0;
      for (let last = left; last <= right; last += 1) {
        const gain =
          padded[left - 1] * padded[last] * padded[right + 1] +
          coins[left][last - 1] +
          coins[last + 1][right];
        if (gain > best) {
          best = gain;
        }
      }
      coins[left][right] = best;
    }
  }
  return coins[1][n];
}

Walkthrough

Pad [3,1,5,8] with 1s. coins[1][4] considers last burst index — splits into independent inner intervals.

Invariant: coins[left][right] is independent of outside balloons; endpoints left-1 and right+1 act as fixed neighbors.

Edge Cases

n = 0 — problem usually n >= 1; if empty, return 0
Single balloon — nums[0] with both neighbors 1

Pitfalls

Prefix DP “burst from left” — wrong dependency order
Forgetting padding ones — boundary multipliers wrong

Variants

Matrix chain multiplication — same interval DP skeleton with different cost model
Remove boxes (LC 546) — colored interval removal — harder state
Minimize coins instead of maximize — flip recurrence to min

Mind-Map Tags

#interval-dp #last-element-split #matrix-chain #pad-sentinel #maximize-coins