Skip to main content
Interval DP

Burst Balloons

Bursting balloon k between i and j gives nums[i]×nums[k]×nums[j] coins. The trick: think of k as the LAST balloon to burst in range, not the first. dp[i][j] = max over all k of (dp[i][k] + dp[k][j] + nums[i]×nums[k]×nums[j]).

O(n³)
·
O(n²)

How It Works

Burst Balloons is interval DP with a reversal trick. Bursting a balloon changes its neighbors, so deciding which balloon pops first entangles subproblems. Instead, fix which balloon k pops last in the open range (i, j): at that moment its neighbors are exactly the boundaries i and j, earning nums[i] × nums[k] × nums[j] coins, and the ranges (i, k) and (k, j) become fully independent. Hence dp[i][j] = max over k of dp[i][k] + dp[k][j] + nums[i]·nums[k]·nums[j].

After padding the array with virtual 1-valued balloons at both ends, you fill ranges from short to long. With O(n^2) intervals and O(n) split points each, the algorithm runs in O(n^3) time and O(n^2) space — versus n! orderings for brute force.

Step-by-Step Visualization

Burst balloons [3,1,5,8] for max coins
3
0
1
1
5
2
8
3
Padded[1, 3, 1, 5, 8, 1]
1/3

Code

Java
static int maxCoins(int[] nums) {
  int n = nums.length + 2;
  int[] arr = new int[n];
  arr[0] = arr[n-1] = 1;
  for (int i = 0; i < nums.length; i++) arr[i+1] = nums[i];
  int[][] dp = new int[n][n];

  for (int len = 2; len < n; len++)
    for (int i = 0; i + len < n; i++) {
      int j = i + len;
      for (int k = i + 1; k < j; k++)
        dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j]);
    }
  return dp[0][n-1];
}

Tips & Gotchas

1Think of k as the LAST balloon to burst in range [i,j]
2dp[i][j] = max coins from bursting all balloons between i and j
3When k is last, its neighbors are i and j (everything else already burst)

Practice Problems

  • 1Burst Balloons
  • 2Minimum Cost to Merge Stones
  • 3Remove Boxes
  • 4Strange Printer

About the Interval DP Pattern

Solve subproblems on every contiguous range [i..j]. The outer loop iterates over range lengths, the inner loops over starting positions. At each range, try every possible split point to find the optimum.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

Why think about the last balloon instead of the first?

If you fix the first balloon to burst, the two remaining sides still interact through their new adjacency, so they are not independent subproblems. Fixing the last balloon pins its neighbors to the fixed range boundaries, cleanly decoupling the left and right intervals.

What role do the padded 1s at the boundaries play?

They give the outermost balloons well-defined neighbors so the coin formula nums[i]·nums[k]·nums[j] works uniformly, including at the edges. The final answer is then dp[0][n+1] over the padded array.

How do I order the loops so subproblems are ready when needed?

Iterate interval length from small to large, then the left endpoint, then the split point k. Since dp[i][j] reads only strictly shorter intervals dp[i][k] and dp[k][j], processing by increasing length guarantees they are already computed.