Burst Balloons: The Paradigm Shift
When Your Correct Intuition Can't Be Memoized: This problem teaches you that sometimes the "obvious" recursive solution, while correct, needs a complete paradigm shift to become DP-able.
The Problem
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. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Examples
// Example 1:
Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
// Example 2:
Input: nums = [1,5]
Output: 10
PART 1: Your ACTUAL Intuition
"Try bursting each balloon, create a NEW array without that balloon, recursively solve for the new array, try ALL possibilities."
This is the natural, correct way to think about this problem!
Let me code YOUR exact intuition:
class Solution {
public int maxCoins(int[] nums) {
List<Integer> balloons = new ArrayList<>();
for (int num : nums) {
balloons.add(num);
}
return burstBalloons(balloons);
}
private int burstBalloons(List<Integer> balloons) {
// Base case: no balloons left
if (balloons.isEmpty()) {
return 0;
}
int maxCoins = 0;
// Try bursting each balloon
for (int i = 0; i < balloons.size(); i++) {
// Calculate coins from bursting balloon i
int left = (i - 1 >= 0) ? balloons.get(i - 1) : 1;
int right = (i + 1 < balloons.size()) ? balloons.get(i + 1) : 1;
int coins = left * balloons.get(i) * right;
// Create new array WITHOUT balloon i
List<Integer> newBalloons = new ArrayList<>(balloons);
newBalloons.remove(i);
// Recurse on the new array
int totalCoins = coins + burstBalloons(newBalloons);
maxCoins = Math.max(maxCoins, totalCoins);
}
return maxCoins;
}
}
PART 2: Testing Your Intuition
Let's trace through [3, 1, 5, 8]:
Initial: [3, 1, 5, 8]
Option 1: Burst 3 first
coins = 1 * 3 * 1 = 3
newArray = [1, 5, 8]
recurse...
Option 2: Burst 1 first
coins = 3 * 1 * 5 = 15
newArray = [3, 5, 8]
recurse...
Option 3: Burst 5 first
coins = 1 * 5 * 8 = 40
newArray = [3, 1, 8]
recurse...
Option 4: Burst 8 first
coins = 5 * 8 * 1 = 40
newArray = [3, 1, 5]
recurse...
The Critical Question
YES! Your intuition is 100% CORRECT!
Run this code—it will give you 167 for [3,1,5,8].
PART 3: So What's the Problem?
Your approach works, but...
Problem 1: The State Space is Exponential
State = "which balloons are left"
[3, 1, 5, 8] → can become:
[1, 5, 8]
[3, 5, 8]
[3, 1, 8]
[3, 1, 5]
Each of those can split further:
[1, 5, 8] → [5, 8], [1, 8], [1, 5]
[3, 5, 8] → [5, 8], [3, 8], [3, 5]
...
How many possible arrays can we create?
With n balloons, we can have 2^n different subsets!
We can't memoize this—the "state" is the entire array configuration!
Problem 2: Can't Define Subproblems Cleanly
WHAT IDENTIFIES A UNIQUE SUBPROBLEM?
Your approach:
- Parameter =
List<Integer> balloons - This is a UNIQUE SEQUENCE each time
- Can't create a DP table for "arbitrary sequences"
The DP Solution (Burst Last):
- Parameters =
(left, right)- two integers representing range boundaries - State: "What is the maximum coins from bursting all balloons in range [left, right]?"
- This CAN be memoized in a 2D table
dp[left][right]
Example:
dp[2][4]= "max coins from bursting balloons at indices 2, 3, 4"- No matter how we arrived at this state, the answer is always the same
- Total states: O(n²) instead of O(2^n)
PART 4: The Paradigm Shift
Why We Need a Different Recursion
You (first attempt): "Try bursting each balloon, pass the new array."
- Works: ✓ Correct answer
- DP-able: ✗ Can't memoize arbitrary arrays
Designer thinks: "I need to represent state with just 2 integers for DP table..."
The insight:
Instead of "which balloons exist," use "which RANGE of balloons am I working on?"
State Representation Comparison
Your way: State = [3, 1, 5] (which balloons are left)
DP way: State = (left=0, right=2) (range in original array)
PART 5: The "Burst Last" Trick
It's Not About Correctness—It's About DP State Definition
- Your approach: ✓ Correct, ✗ Can't be memoized
- "Burst last" approach: ✓ Correct, ✓ Can be memoized
The Deep Insight
When you remove balloons from an array:
[3, 1, 5, 8] → burst 1 → [3, 5, 8]
[3, 1, 5, 8] → burst 3, then 1 → [5, 8]
Same resulting array [5, 8], but DIFFERENT histories!
These should give the SAME answer (they're the same subproblem), but in your recursion they're separate calls with separate paths.
When you use "burst last in a range":
State = (left=2, right=3) means "balloons from index 2 to 3"
No matter HOW we got here, (left=2, right=3) always means the same thing!
This allows memoization!
PART 6: Both Approaches Side-by-Side
Your Approach (Can't Memoize)
// State = the actual list of remaining balloons
// Can't create dp[???] because state is dynamic
private int burstBalloons(List<Integer> balloons) {
if (balloons.isEmpty()) return 0;
int maxCoins = 0;
for (int i = 0; i < balloons.size(); i++) {
int left = (i - 1 >= 0) ? balloons.get(i - 1) : 1;
int right = (i + 1 < balloons.size()) ? balloons.get(i + 1) : 1;
int coins = left * balloons.get(i) * right;
List<Integer> newBalloons = new ArrayList<>(balloons);
newBalloons.remove(i);
maxCoins = Math.max(maxCoins, coins + burstBalloons(newBalloons));
}
return maxCoins;
}
"Burst Last" Approach (Can Memoize)
// State = (left, right) two integers
// CAN create dp[left][right]
private int burstLast(int[] arr, int left, int right, int[][] memo) {
if (left > right) return 0;
if (memo[left][right] != -1) {
return memo[left][right];
}
int maxCoins = 0;
// Try bursting each balloon i as the LAST one in this range
for (int i = left; i <= right; i++) {
// When i bursts LAST, all others in [left, right] are already gone
// So i's neighbors are arr[left-1] and arr[right+1]
int coins = arr[left-1] * arr[i] * arr[right+1];
// Add coins from bursting balloons before i and after i
coins += burstLast(arr, left, i-1, memo);
coins += burstLast(arr, i+1, right, memo);
maxCoins = Math.max(maxCoins, coins);
}
memo[left][right] = maxCoins;
return maxCoins;
}
PART 7: The Prerequisites - What You Need to See
1. Why "Burst Last" Fixes the State Problem
When I'm solving range [2, 4], why don't I need to know what happened outside this range?
Because we're deciding which balloon in [2, 4] bursts LAST!
- When balloon
ibursts last, ALL others in[2, 4]are already gone - So balloon
i's neighbors arearr[1]andarr[5](the boundaries) - Those boundaries don't change based on the ORDER we burst things inside
[2, 4]
2. Your Approach vs "Burst Last" - Same Tree, Different View
Your recursion tree:
[3,1,5,8]
/ | \
[1,5,8] [3,5,8] [3,1,8] ...
"Burst last" recursion tree:
(0, 3) = range of indices
/ | \ \
i=0 last | i=1 last | i=2 last | i=3 last
Same exploration, but "burst last" uses indices instead of arrays!
PART 8: Complete Solution
The Setup
We add 1 at both ends to handle boundary conditions cleanly.
// Original: [3, 1, 5, 8]
// Padded: [1, 3, 1, 5, 8, 1]
This way we never have to check if (i-1 < 0) or if (i+1 >= length).
Full Implementation
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
// Create padded array with 1s at both ends
int[] arr = new int[n + 2];
arr[0] = 1;
arr[n + 1] = 1;
for (int i = 0; i < n; i++) {
arr[i + 1] = nums[i];
}
// Create memoization table
int[][] memo = new int[n + 2][n + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
memo[i][j] = -1;
}
}
// Solve for range [1, n] (excluding the padding)
return burst(arr, 1, n, memo);
}
private int burst(int[] arr, int left, int right, int[][] memo) {
// Base case: no balloons in this range
if (left > right) {
return 0;
}
// Check memo
if (memo[left][right] != -1) {
return memo[left][right];
}
int maxCoins = 0;
// Try bursting each balloon i as the LAST one in range [left, right]
for (int i = left; i <= right; i++) {
// Coins from bursting balloon i LAST
// When i is last, all others are gone, so neighbors are arr[left-1] and arr[right+1]
int coins = arr[left - 1] * arr[i] * arr[right + 1];
// Add coins from left and right subproblems
coins += burst(arr, left, i - 1, memo);
coins += burst(arr, i + 1, right, memo);
maxCoins = Math.max(maxCoins, coins);
}
memo[left][right] = maxCoins;
return maxCoins;
}
}
PART 9: Trace Through Example
nums = [3, 1, 5, 8]Padded array: [1, 3, 1, 5, 8, 1]
Solving burst(1, 4) (range containing [3, 1, 5, 8]):
Try bursting each balloon LAST:
Option 1: Balloon at index 1 (value 3) bursts LAST
coins = arr[0] * arr[1] * arr[5] // 1 * 3 * 1 = 3
+ burst(1, 0) // 0 (empty range)
+ burst(2, 4) // solve [1, 5, 8]
Option 2: Balloon at index 2 (value 1) bursts LAST
coins = arr[0] * arr[2] * arr[5] // 1 * 1 * 1 = 1
+ burst(1, 1) // solve [3]
+ burst(3, 4) // solve [5, 8]
Option 3: Balloon at index 3 (value 5) bursts LAST
coins = arr[0] * arr[3] * arr[5] // 1 * 5 * 1 = 5
+ burst(1, 2) // solve [3, 1]
+ burst(4, 4) // solve [8]
Option 4: Balloon at index 4 (value 8) bursts LAST
coins = arr[0] * arr[4] * arr[5] // 1 * 8 * 1 = 8
+ burst(1, 3) // solve [3, 1, 5]
+ burst(5, 4) // 0 (empty range)
The recursion continues until all subproblems are solved, with memoization preventing redundant calculations.
Result: 167
PART 10: The Time Complexity Revelation
Your Approach
Time: O(n! × n) in worst case
- n! ways to order bursting
- Each path is length n
Space: O(n) recursion depth
Can't improve with memoization: State is too complex
"Burst Last" Approach
Time without memo: O(n! × n) same as yours!
Time WITH memo: O(n³)
- O(n²) states: (left, right) pairs
- O(n) work per state: the for loop
Space: O(n²) for DP table
From O(n!) to O(n³) with memoization!
PART 11: Edge Case Verification
Does Your Approach Work?
// Test: [3, 1, 5, 8]
// Expected: 167
// Your code will explore:
// 3*1*5 + recurse([3,5,8])
// 3*5*8 + recurse([3,8])
// 1*3*8 + recurse([8])
// 1*8*1 + recurse([])
// Total: 15 + 120 + 24 + 8 = 167 ✓ CORRECT!
Your approach is correct, just inefficient!
PART 12: The Meta-Lesson
The Designer's Journey
-
Brute force that works (Your intuition)
- Try everything
- Use simple state (the actual array)
-
Notice inefficiency
- "I'm recalculating the same subproblems..."
- "But I can't memoize because state is too complex..."
-
Rethink the state representation
- "What if I use indices instead of arrays?"
- "What if I think backward (last to burst)?"
-
Discover the DP formulation
- State reduces from O(2^n) configurations to O(n²) ranges
- Can memoize!
Your Questions Answered
YES! Your intuition is spot-on for correctness.
NO! Because you can't efficiently memoize List<Integer> as a state.
The key insight: We need to rethink the problem NOT for correctness, but for memoizability.
Test Your Understanding
-
Why can't we memoize your approach directly?
-
In your approach with
[3,1,5,8], if we burst them in order 1→5→3→8, what's the coin sequence? -
Why does "burst last" allow us to use just two integers (left, right) as state?
-
What would happen if we tried "burst first" instead of "burst last"? Would it work?
Complexity Analysis
| Metric | Value | Explanation |
|---|---|---|
| Time | O(n³) | O(n²) states × O(n) work per state |
| Space | O(n²) | Memoization table |
Pattern Recognition
This problem teaches a crucial pattern:
When the natural state is "which elements remain" but that's exponential, try thinking in terms of "which range am I working on" and "which element is first/last in this range"
Similar Problems:
- Remove Boxes (same "burst last" pattern)
- Minimum Cost to Merge Stones (range DP with "merge last")
- Strange Printer (interval DP with optimization)
Final Thoughts
This problem is about learning to see the SAME problem from a different angle.
Your recursion was correct.
The DP version is the same recursion, just viewed through the lens of "ranges and burst-last" instead of "actual remaining elements".
That's the paradigm shift.