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 indexland indexr. - 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 pointkinside 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 betweenlandr, whilelandrstill 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 ofnitems.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
kfirst glues its left and right neighbours together, so the two sides still affect each other. - Memoizing on the set of leftover balloons needs
2^nstates: still hopeless forn = 300.
The key insight: the LAST balloon is a wall
Pick the balloon k that bursts last in a window (l, r).
- While everything else in the window bursts,
kis 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). - When
kfinally bursts, everything else is gone: its neighbours are the window's walls, so it paysa[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
- Why does thinking about the first burst fail? After it, its two neighbours become adjacent, so the left and right parts still interact.
- 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.
- State and recurrence?
dp[l][r] = max_k dp[l][k] + a[l]·a[k]·a[r] + dp[k][r], wallslandrexclusive. - Why pad with 1s? It turns "out of range counts as 1" into ordinary array reads and gives the outer walls.
- Fill order? By window length; any order where
dp[l][k]anddp[k][r]are ready works (e.g.lfrom big to small,rfrom small to big). - Complexity? O(n³) time, O(n²) space.
- 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; answerdp[0][n + 1]. - O(n³) time, O(n²) space.
- Next episode: matrix chain multiplication, where the last product splits the chain: interval DP again.