Burst Balloons

Problem

You have n balloons with values nums[0..n]. Bursting balloon i gains nums[i - 1] * nums[i] * nums[i + 1] coins, using the current neighbors (bursting removes the balloon and merges the neighbors). Out-of-range neighbors count as 1. Return the maximum coins.

Intuition

The hard part of this problem is that the natural recurrence goes the wrong way. If you try to frame it as "which balloon do I burst first in interval (l, r)?", the sub-intervals you'd recurse into depend on the balloon's neighbors after bursting — which depend on what's in the complement of the current interval. The sub-problems aren't independent, so DP stalls.

The reframe: which balloon do I burst last in interval (l, r)?

If balloon k is the last one in (l, r) to pop, then at the moment it bursts, its neighbors are exactly l and r — by definition, everything strictly between l and r has already been burst. And the two sides (l, k) and (k, r) are now fully independent of each other and of what's outside (l, r). That's what makes the DP work.

Pad nums with 1 on both sides (call the padded array v of length n + 2). Then:

dp[l][r] = max_{k in (l, r)} dp[l][k] + dp[k][r] + v[l] * v[k] * v[r]

Base: dp[l][r] = 0 when r - l < 2 (no balloons strictly between endpoints). Answer: dp[0][n + 1].

Iterate by increasing interval length so sub-intervals are filled when you need them.

Approach

impl Solution {
    pub fn max_coins(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 0 {
            return 0;
        }
        // Pad with 1s at both ends.
        let mut v = Vec::with_capacity(n + 2);
        v.push(1);
        v.extend(nums.iter().copied());
        v.push(1);
        let m = v.len();
        let mut dp = vec![vec![0i32; m]; m];
        for len in 2..m {
            for l in 0..(m - len) {
                let r = l + len;
                let mut best = 0;
                for k in (l + 1)..r {
                    let coins = dp[l][k] + dp[k][r] + v[l] * v[k] * v[r];
                    if coins > best {
                        best = coins;
                    }
                }
                dp[l][r] = best;
            }
        }
        dp[0][m - 1]
    }
}

function maxCoins(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;
  const v = [1, ...nums, 1];
  const m = v.length;
  const dp: number[][] = Array.from({ length: m }, () => new Array(m).fill(0));
  for (let len = 2; len < m; len++) {
    for (let l = 0; l + len < m; l++) {
      const r = l + len;
      let best = 0;
      for (let k = l + 1; k < r; k++) {
        const coins = dp[l][k] + dp[k][r] + v[l] * v[k] * v[r];
        if (coins > best) best = coins;
      }
      dp[l][r] = best;
    }
  }
  return dp[0][m - 1];
}

Trace

Intermediate intervals for nums = [3, 1, 5, 8] → padded v = [1, 3, 1, 5, 8, 1] (indices 0–5):

Return dp[0][5] = 167. ✓

Edge cases

• Empty nums — return 0. Early exit handles this without entering the DP.
• Single balloon — return nums[0]. Pad → [1, x, 1]; the only k gives 1 * x * 1 = x.
• All ones — dp[0][n + 1] = n (each burst contributes 1). The DP confirms.
• Very negative or zero values — LC guarantees 0 ≤ nums[i] ≤ 100. If zeros appear, the reframe still works (zero-products are just small); max stays correct because dp[l][r] = 0 is always a lower bound.

Takeaway

Burst Balloons is the reference problem for the "last X" interval-DP reframe. If the forward recurrence tangles sub-problems by making their boundaries depend on each other, check whether reasoning backwards makes the sides independent. Here the trick is stark — bursting order matters, but "which one bursts last" always isolates the surrounding values.

Interval DPs are templated: pad (if endpoints matter), fill by increasing length, iterate over the split point, take the min/max. Learn this template on #312 and #1130; extend it to #1547 (cut stick) next. Every interval-DP problem after is a variation on which quantity you accumulate across the split.