9.9 Interval DP

Demo: Burst Balloons — LC 312 (Hard — Google/Meta High)

Statement (Demo): nums[i] is the number on balloon i. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] (out-of-range neighbours count as 1). Return the most coins from bursting all balloons. Example: nums=[3,1,5,8] → 167 | ⚡ n ≤ 300

Approach: Think backwards — inside the open interval (l, r), which balloon k bursts last? At that moment its neighbours are l and r themselves. dp[l][r] = max(dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]). Pad both ends with 1.

function maxCoins(nums) {
  const a = [1, ...nums, 1];
  const n = a.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 2; len < n; len++) {
    for (let l = 0; l + len < n; l++) {
      const r = l + len;
      for (let k = l + 1; k < r; k++) {
        // k = the balloon burst last
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]);
      }
    }
  }
  return dp[0][n - 1];
}

Complexity: Time O(n³), Space O(n²)