🗓️ Day 40: Hard DP — Burst Balloons Problem

🧠 Concept Deep Dive

You're given an array of balloons, each with a number. When you burst a balloon i, you gain coins equal to nums[i-1] * nums[i] * nums[i+1]. Your task: burst all balloons in optimal order to maximize total coins.

This is a hard interval DP problem.

We insert virtual balloons with value 1 at both ends to avoid edge cases: nums = [1, ...original..., 1].

Let dp[i][j] be the maximum coins obtainable by bursting balloons between i and j (exclusive).

🎯 Visual Intuition

Let’s say:

nums = [3, 1, 5, 8]

We pad:

[1, 3, 1, 5, 8, 1]

We try all possible last balloons to burst in any interval (i, j) and combine the subresults.

🛠️ Code Pattern: Interval DP

function maxCoins(nums: number[]): number {
  const n = nums.length;
  const arr = [1, ...nums, 1];
  const dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));

  for (let len = 2; len < n + 2; len++) {
    for (let left = 0; left < n + 2 - len; left++) {
      const right = left + len;
      for (let k = left + 1; k < right; k++) {
        dp[left][right] = Math.max(
          dp[left][right],
          arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right]
        );
      }
    }
  }

  return dp[0][n + 1];
}

📘 Example

Input: [3, 1, 5, 8]
Output: 167

Explanation:
- Burst order: 1, 5, 3, 8
- Coins: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167

🧪 Homework

Can you reconstruct the bursting order using parent pointer?
What if there are many 1s in the array — how does it affect choice?
Try the brute-force approach with recursion + memoization.

🧠 Big-O Cheat Sheet

Time: O(N^3) — three nested loops
Space: O(N^2) for dp table

🔮 Up Next

▶️ Day 41: Bit Manipulation — Single Number Problems