05. Burst Balloons

Difficulty:HardPattern:Interval DPTime:O(n^3)Space:O(n^2)

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. If you burst balloon i you will get nums[i - 1] * nums[i] * nums[i + 1] coins. Return the maximum coins you can collect.

How It Works & Algorithmic Design

Solves using Reverse Interval Dynamic Programming:

Padding: Pad input nums with $1$ at both ends: [1, ...nums, 1].
Reverse Decision: Think of picking the LAST balloon $k$ to burst in interval [i, j]:
- Coins gained from picking balloon $k$ last = nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j].
DP Interval Loop: Expand sub-array length len from $1$ to $n$, evaluating all choices of $k$ to maximize total coins.

Why This Approach Works Best

Reversing decision order makes sub-problems independent, solving the problem in $O(n^3)$ time and $O(n^2)$ space.

Example Walkthrough

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

Balloons list.

Optimal Sequence: Burst 1 -> Burst 5 -> Burst 3 -> Burst 8

Yields 167 total coins.

Output: 167

Maximum coins.

Answer: Burst Balloons Interval DP implementation

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 = 1; len <= nums.length; len++) {
    for (let i = 1; i <= nums.length - len + 1; i++) {
      const j = i + len - 1;
      for (let k = i; k <= j; k++) {
        dp[i][j] = Math.max(dp[i][j], A[i - 1] * A[k] * A[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
      }
    }
  }
  return dp[1][nums.length];
}

💡 Compute optimal coins bottom-up across sub-array lengths by determining the last balloon to burst.

Key Takeaways

Reversing decision logic (selecting last burst balloon) keeps sub-problems decoupled.
Pad boundary array with 1 at both index ends.
Time complexity $O(n^3)$.