SyntaxPilot
Courses/DSA and Coding Problems/Lesson 74
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 74 of 90

Burst balloons: interval DP (hard)

queued

These are the notes for DSA episode 74. At a mela balloon stall, bursting a balloon pays left neighbour × balloon × right neighbour coins, and every burst changes who the neighbours are. In which order do you win the most? We try smallest first (a wrong answer on screen: 78 instead of 167), then every order recursively (correct, then Time Limit Exceeded on just 13 balloons), see why choosing the first balloon never splits the problem, and find the key insight: choose the last balloon in a window. It stands like a wall while everything else bursts, so the left and right windows are independent. That is interval DP, typed live, then 500 balloons in milliseconds and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The balloon stall In code
A row of numbered balloons the array nums
Burst one: left × it × right coins nums[left] * nums[i] * nums[right]
Past either end, an invisible balloon of 1 padding: a = [1, nums..., 1]
The neighbours change after each burst the order matters
Burst all, win the most return the maximum total

Every word, from zero

  • Interval (window): a range of positions (l, r). Here the balloons strictly between index l and index r.
  • Wall: a balloon that is still standing at the ends of a window. The padded 1s are permanent walls.
  • Padding: adding extra values at the ends of an array so edge cases disappear (a[0] = a[n + 1] = 1).
  • Interval DP: dynamic programming where the state is a range (l, r) and the answer comes from a split point k inside it.
  • Split point k: the balloon we decide bursts last in the window.
  • Independent subproblems: two parts whose answers don't affect each other, so you can solve each one alone and add them.
  • State: dp[l][r] = most coins from bursting every balloon strictly between l and r, while l and r still stand.
  • Recurrence: dp[l][r] = max over k of dp[l][k] + a[l]·a[k]·a[r] + dp[k][r].
  • Base case: a window with nothing inside (r = l + 1) gives 0.
  • Fill order: by window length, so shorter windows are ready before longer ones need them.
  • Factorial (n!): n × (n−1) × ... × 1, the number of orders of n items. 13! ≈ 6.2 billion.

Problem statement

Burst Balloons (LeetCode 312). You are given n balloons with numbers nums[i]. Bursting balloon i gives nums[i − 1] × nums[i] × nums[i + 1] coins, using its current neighbours; out of range counts as 1. Burst all balloons and return the maximum coins. 1 ≤ n ≤ 300, 0 ≤ nums[i] ≤ 100.

nums Answer Best order
[3, 1, 5, 8] 167 1, 5, 3, 8: 15 + 120 + 24 + 8
[1, 5] 10 1 then 5: 5 + 5
[7] 7 1 × 7 × 1
[] 0 nothing to burst
[2, 2, 2] 14 middle, then one, then the last: 8 + 4 + 2

Obvious idea 1: burst the smallest first

Small numbers pay little, so get rid of them first?

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        List<Integer> b = new ArrayList<>();
        for (int x : nums) b.add(x);
        int total = 0;
        while (!b.isEmpty()) {
            int i = b.indexOf(Collections.min(b));
            int left = i == 0 ? 1 : b.get(i - 1);
            int right = i == b.size() - 1 ? 1 : b.get(i + 1);
            total += left * b.get(i) * right;
            b.remove(i);
        }
        return total;
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(maxCoins(new int[]{1, 5}));
    }
}
78
10

78 instead of 167. Bursting the 3 early threw away a big neighbour for later bursts. A cheap burst now changes every later burst; no simple rule gets it right.

Obvious idea 2: try every order

best(list) tries each balloon as the next burst, adds its coins, and recurses on the list without it.

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        List<Integer> b = new ArrayList<>();
        for (int x : nums) b.add(x);
        return best(b);
    }
    static int best(List<Integer> b) {
        if (b.isEmpty()) return 0;
        int most = 0;
        for (int i = 0; i < b.size(); i++) {
            int left = i == 0 ? 1 : b.get(i - 1);
            int right = i == b.size() - 1 ? 1 : b.get(i + 1);
            List<Integer> rest = new ArrayList<>(b);
            rest.remove(i);
            most = Math.max(most, left * b.get(i) * right + best(rest));
        }
        return most;
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(maxCoins(new int[]{1, 5}));
        System.out.println(maxCoins(new int[]{7}));
        System.out.println(maxCoins(new int[]{}));
        System.out.println(maxCoins(new int[]{2, 2, 2}));
    }
}
167
10
7
0
14

Correct. Now 13 balloons:

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        List<Integer> b = new ArrayList<>();
        for (int x : nums) b.add(x);
        return best(b);
    }
    static int best(List<Integer> b) {
        if (b.isEmpty()) return 0;
        int most = 0;
        for (int i = 0; i < b.size(); i++) {
            int left = i == 0 ? 1 : b.get(i - 1);
            int right = i == b.size() - 1 ? 1 : b.get(i + 1);
            List<Integer> rest = new ArrayList<>(b);
            rest.remove(i);
            most = Math.max(most, left * b.get(i) * right + best(rest));
        }
        return most;
    }
    public static void main(String[] args) {
        int[] nums = new int[13];
        for (int i = 0; i < 13; i++) nums[i] = i % 9 + 1;
        long t0 = System.nanoTime();
        int c = maxCoins(nums);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("13 balloons: " + c + " coins, " + ms + " ms");
    }
}

(no output: still running after 25 s: Time Limit Exceeded)

Why is it slow?

  • It tries every order: 13! ≈ 6.2 billion.
  • Divide and conquer doesn't work with the first burst: bursting k first glues its left and right neighbours together, so the two sides still affect each other.
  • Memoizing on the set of leftover balloons needs 2^n states: still hopeless for n = 300.

The key insight: the LAST balloon is a wall

Pick the balloon k that bursts last in a window (l, r).

  1. While everything else in the window bursts, k is still standing, so balloons on its left only ever see neighbours on its left, and balloons on its right only see the right: two independent windows, (l, k) and (k, r).
  2. When k finally bursts, everything else is gone: its neighbours are the window's walls, so it pays a[l] × a[k] × a[r].
dp[l][r] = max over l < k < r of   dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]
dp[l][l + 1] = 0                   (nothing inside)
answer = dp[0][n + 1]              (between the two padded walls)

By hand: [3, 1, 5, 8], padded to [1, 3, 1, 5, 8, 1]

Window (l, r) Balloons inside Best last k dp
(0, 2) 3 3 1·3·1 = 3
(1, 3) 1 1 3·1·5 = 15
(2, 4) 5 5 1·5·8 = 40
(3, 5) 8 8 5·8·1 = 40
(0, 3) 3, 1 3 0 + 1·3·5 + 15 = 30
(1, 4) 1, 5 5 15 + 3·5·8 + 0 = 135
(2, 5) 5, 8 8 40 + 1·8·1 + 0 = 48
(0, 4) 3, 1, 5 3 0 + 1·3·8 + 135 = 159
(1, 5) 1, 5, 8 8 135 + 3·8·1 + 0 = 159
(0, 5) all four 8 159 + 1·8·1 + 0 = 167

Reading the choices back: 8 is last overall; in (0, 4) the 3 is last; in (1, 4) the 5 is last; so the 1 bursts first. Order: 1, 5, 3, 8.

Solution in Java

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        a[0] = 1;
        a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 2; len <= n + 1; len++)
            for (int l = 0; l + len <= n + 1; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++)
                    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];
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(maxCoins(new int[]{1, 5}));
        System.out.println(maxCoins(new int[]{7}));
        System.out.println(maxCoins(new int[]{}));
        System.out.println(maxCoins(new int[]{2, 2, 2}));
    }
}
167
10
7
0
14

The 13 balloons that timed out, and 300 and 500 random balloons:

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        a[0] = 1;
        a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 2; len <= n + 1; len++)
            for (int l = 0; l + len <= n + 1; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++)
                    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];
    }
    public static void main(String[] args) {
        int[] nums = new int[13];
        for (int i = 0; i < 13; i++) nums[i] = i % 9 + 1;
        long t0 = System.nanoTime();
        int c = maxCoins(nums);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("13 balloons: " + c + " coins, " + ms + " ms");
        for (int n : new int[]{300, 500}) {
            int[] big = new int[n];
            Random rnd = new Random(1);
            for (int i = 0; i < n; i++) big[i] = rnd.nextInt(101);
            t0 = System.nanoTime();
            c = maxCoins(big);
            ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(n + " balloons: " + c + " coins, " + ms + " ms");
        }
    }
}
13 balloons: 1768 coins, 0 ms
300 balloons: 103989941 coins, 22 ms
500 balloons: 176531033 coins, 36 ms

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Burst balloons: dp[l][r] = most coins from the balloons strictly between walls l and r.
int maxCoins(const vector<int>& nums) {
    int n = nums.size();
    vector<int> a(n + 2, 1);                       // walls of 1 at index 0 and n + 1
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 2; len <= n + 1; len++)         // short windows first
        for (int l = 0; l + len <= n + 1; l++) {
            int r = l + len;
            for (int k = l + 1; k < r; k++)        // k bursts LAST in (l, r)
                dp[l][r] = max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]);
        }
    return dp[0][n + 1];
}

int main() {
    cout << maxCoins({3, 1, 5, 8}) << "\n";
    cout << maxCoins({1, 5}) << "\n";
    cout << maxCoins({7}) << "\n";
    cout << maxCoins({}) << "\n";
    cout << maxCoins({2, 2, 2}) << "\n";
}
167
10
7
0
14

The same solution in Python

# Burst balloons: dp[l][r] = most coins from the balloons strictly between walls l and r.
def max_coins(nums):
    a = [1] + nums + [1]                     # walls of 1 at both ends
    m = len(a)
    dp = [[0] * m for _ in range(m)]
    for length in range(2, m):               # short windows first
        for l in range(0, m - length):
            r = l + length
            dp[l][r] = max(dp[l][k] + a[l] * a[k] * a[r] + dp[k][r] for k in range(l + 1, r))
    return dp[0][m - 1]

print(max_coins([3, 1, 5, 8]))
print(max_coins([1, 5]))
print(max_coins([7]))
print(max_coins([]))
print(max_coins([2, 2, 2]))
167
10
7
0
14

Three real bugs

Bug 1: the walls are never set to 1. new int[n + 2] is all zeros, so every coin that touches a wall becomes 0.

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 2; len <= n + 1; len++)
            for (int l = 0; l + len <= n + 1; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++)
                    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];
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(maxCoins(new int[]{7}));
    }
}
135
0

Bug 2: loops by left wall, then right wall. When l = 0, dp[k][r] for a bigger left wall k hasn't been filled yet (it is still 0).

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        a[0] = 1;
        a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int l = 0; l <= n + 1; l++)
            for (int r = l + 2; r <= n + 1; r++) {
                for (int k = l + 1; k < r; k++)
                    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];
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(maxCoins(new int[]{1, 5}));
    }
}
63
10

Bug 3: a table of n + 1 by n + 1. The right wall is index n + 1, so the table needs n + 2 places.

import java.util.*;

public class Main {
    static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        a[0] = 1;
        a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 2; len <= n + 1; len++)
            for (int l = 0; l + len <= n + 1; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++)
                    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];
    }
    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
    at Main.maxCoins(Main.java:15)
    at Main.main(Main.java:21)

Complexity

Approach Time Space Big input
Smallest first O(n²) O(n) fast but wrong
Every order O(n!) O(n²) for the copied lists 13 balloons: Time Limit Exceeded
Interval DP O(n³) O(n²) 500 balloons: ~25 ms

About n²/2 windows, each trying up to n choices of k: for n = 300, roughly 4.5 million steps.

Common mistakes

Mistake What you see (real) Why Fix
Smallest first (greedy) 78 instead of 167 a cheap burst now costs later try every k as the last
Thinking about the first burst no clean recurrence its neighbours glue together choose the last balloon
Walls not set 135, and 0 for [7] new int[] is all zeros a[0] = a[n + 1] = 1
Loop l, then r 63 instead of 167 reads dp[k][r] before it is filled loop by window length
new int[n + 1][n + 1] ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 the walls need n + 2 places [n + 2][n + 2]
k from l to r inclusive uses a wall as a balloon walls are never burst l < k < r

Mini project: the stall's best order

Extend the solution with a choice[l][r] table that stores the best last balloon k, then print the actual bursting order (recursively: burst everything in (l, k), then everything in (k, r), then k). Check that the coins you add up along that order equal dp[0][n + 1].

Practice

1. Min Cost to Cut a Stick (LeetCode 1547). A stick of length n must be cut at given positions; a cut costs the current piece's length. Sort the cuts, add 0 and n as walls, and use interval DP. (Here the split k is the first cut of the piece: after it, the two pieces are independent.)

2. Remove Boxes (LeetCode 546) and 3. Strange Printer (LeetCode 664). Harder interval DPs that need an extra dimension.

4. Fill the table for [2, 3, 4].

Solutions (1 and 4)
import java.util.*;

public class Main {
    // Min Cost to Cut a Stick (LeetCode 1547): sort the cuts, add the two ends as walls,
    // dp[i][j] = cheapest way to make every cut strictly between wall i and wall j.
    // The FIRST cut inside a piece costs the piece's length; then the two pieces are independent.
    static int minCost(int n, int[] cuts) {
        int m = cuts.length;
        int[] c = new int[m + 2];
        c[0] = 0;
        c[m + 1] = n;
        int[] s = cuts.clone();
        Arrays.sort(s);
        for (int i = 0; i < m; i++) c[i + 1] = s[i];
        int[][] dp = new int[m + 2][m + 2];
        for (int len = 2; len <= m + 1; len++)
            for (int i = 0; i + len <= m + 1; i++) {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + c[j] - c[i]);
            }
        return dp[0][m + 1];
    }
    // Homework 4: the table for [2, 3, 4], printed window by window.
    static void table(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];
        a[0] = 1;
        a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 2; len <= n + 1; len++)
            for (int l = 0; l + len <= n + 1; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++)
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]);
                System.out.println("dp[" + l + "][" + r + "] = " + dp[l][r]);
            }
    }
    public static void main(String[] args) {
        System.out.println(minCost(7, new int[]{1, 3, 4, 5}));
        System.out.println(minCost(9, new int[]{5, 6, 1, 4, 2}));
        table(new int[]{2, 3, 4});
    }
}
16
22
dp[0][2] = 6
dp[1][3] = 24
dp[2][4] = 12
dp[0][3] = 32
dp[1][4] = 32
dp[0][4] = 36

For [2, 3, 4] the answer is dp[0][4] = 36: burst the 3 first (2·3·4 = 24), then the 2 (1·2·4 = 8), then the 4 (1·4·1 = 4).

Quick quiz

maxCoins(new int[]{2, 3}) returns? A) 6 B) 8 C) 9 D) 12

Answer

C) 9. Burst 2 first: 1·2·3 = 6, then 3 alone: 3. Total 9. The other order gives 2·3·1 = 6, then 2 = 8.

Interview questions

  1. Why does thinking about the first burst fail? After it, its two neighbours become adjacent, so the left and right parts still interact.
  2. Why does the last balloon work? It stands until the end, acting as a wall: the two sides never see each other, and when it bursts its neighbours are exactly the window's walls.
  3. State and recurrence? dp[l][r] = max_k dp[l][k] + a[l]·a[k]·a[r] + dp[k][r], walls l and r exclusive.
  4. Why pad with 1s? It turns "out of range counts as 1" into ordinary array reads and gives the outer walls.
  5. Fill order? By window length; any order where dp[l][k] and dp[k][r] are ready works (e.g. l from big to small, r from small to big).
  6. Complexity? O(n³) time, O(n²) space.
  7. Where else does interval DP appear? Matrix chain multiplication, minimum cost to cut a stick, polygon triangulation, palindrome partitioning.

Glossary

Term Meaning
Interval / window The range of positions strictly between l and r
Wall A balloon still standing at a window's end; the padded 1s are permanent walls
Padding Extra values added at the array's ends (1 here)
Interval DP DP whose state is a range, solved via a split point inside it
Split point k The balloon that bursts last in the window
Independent subproblems Parts whose answers don't affect each other
State dp[l][r]: most coins from the balloons between l and r
Recurrence max_k dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]
Base case An empty window gives 0
Greedy Always taking the choice that looks best right now
Factorial n!, the number of orders of n items

Summary

  • Greedy orders give wrong answers; trying every order is correct but O(n!).
  • Bursting a balloon first glues its sides together; bursting it last makes it a wall and splits the window into two independent ones.
  • Pad with 1s; dp[l][r] = max_k dp[l][k] + a[l]·a[k]·a[r] + dp[k][r], filled by window length; answer dp[0][n + 1].
  • O(n³) time, O(n²) space.
  • Next episode: matrix chain multiplication, where the last product splits the chain: interval DP again.