Burst Balloons
The briefingthe full drill, in my own words
The drill: Balloons in a row each carry a number; bursting one pays its value times the values of its current left and right neighbors, and the row closes up afterward. Choose a bursting order that maximizes total coins collected.
A row of balloons arrives, each printed with a number. Popping one pays out the printed value of that balloon times the values of whichever balloons are currently its immediate left and right neighbors — and the row closes the gap right after.
Because bursting a balloon changes who becomes neighbors with whom, the order balloons are popped in changes the total payout. The task is choosing a popping order — every balloon eventually goes — that maximizes coins collected overall.
The row's two open ends behave as if an invisible balloon worth 1 sits just off each edge, so an end balloon still has two neighbors to multiply against when it goes.
- every balloon must eventually be burst — the row always ends empty
- balloon values are small non-negative numbers, arrays sized modestly
- boundary balloons off each end of the row count as value 1 during scoring
- the payout to maximize is the running total across every burst, not any single pop
The hintstake only what you need
HINT 1 THE NUDGE
Thinking about which balloon to burst first is a trap — bursting it changes who's adjacent to everyone else, so the leftover subproblems aren't independent. What if instead you decided which balloon burst LAST inside a stretch of the row?
HINT 2 THE STRUCTURE
If balloon k is the last one burst within an open interval (l, r), then at that moment its neighbors are still whichever balloons stand at the interval's own ends — l and r — no matter what already happened in between. The interval splits cleanly around k.
HINT 3 ONE STEP FROM THE ANSWER
dp(l, r) = the most coins from bursting everything strictly between l and r, leaving l and r themselves unburst. dp(l, r) = max over k in (l, r) of dp(l,k) + dp(k,r) + val[l]·val[k]·val[r]. Pad the row with a 1 on each end as permanent boundary balloons.
Coach's boardthe pattern, step by step
Balloons padded to [1,4,2,6,3,1]. dp(l,r) is the most coins from bursting everything strictly between l and r. Adjacent pairs have nothing between — 0.
The splitstwo paces, two languages
class Solution:
def maxCoins(self, nums: List[int]) -> int:
balloons = [1] + nums + [1]
n = len(balloons)
memo = {}
def dp(l, r):
if r - l < 2:
return 0
if (l, r) in memo:
return memo[(l, r)]
best = 0
for k in range(l + 1, r):
best = max(best, dp(l, k) + dp(k, r) + balloons[l] * balloons[k] * balloons[r])
memo[(l, r)] = best
return best
return dp(0, n - 1)class Solution:
def maxCoins(self, nums: List[int]) -> int:
def rec(balloons):
if not balloons:
return 0
best = 0
for i in range(len(balloons)):
left = balloons[i - 1] if i > 0 else 1
right = balloons[i + 1] if i < len(balloons) - 1 else 1
gained = left * balloons[i] * right
remaining = balloons[:i] + balloons[i + 1:]
best = max(best, gained + rec(remaining))
return best
return rec(nums)class Solution {
private int[] balloons;
private Integer[][] memo;
public int maxCoins(int[] nums) {
int n = nums.length;
balloons = new int[n + 2];
balloons[0] = 1;
balloons[n + 1] = 1;
for (int i = 0; i < n; i++) balloons[i + 1] = nums[i];
memo = new Integer[n + 2][n + 2];
return dp(0, n + 1);
}
private int dp(int l, int r) {
if (r - l < 2) return 0;
if (memo[l][r] != null) return memo[l][r];
int best = 0;
for (int k = l + 1; k < r; k++) {
best = Math.max(best, dp(l, k) + dp(k, r) + balloons[l] * balloons[k] * balloons[r]);
}
memo[l][r] = best;
return best;
}
}class Solution {
public int maxCoins(int[] nums) {
List<Integer> balloons = new ArrayList<>();
for (int v : nums) balloons.add(v);
return rec(balloons);
}
private int rec(List<Integer> balloons) {
if (balloons.isEmpty()) return 0;
int best = 0;
for (int i = 0; i < balloons.size(); i++) {
int left = i > 0 ? balloons.get(i - 1) : 1;
int right = i < balloons.size() - 1 ? balloons.get(i + 1) : 1;
int gained = left * balloons.get(i) * right;
List<Integer> remaining = new ArrayList<>(balloons);
remaining.remove(i);
best = Math.max(best, gained + rec(remaining));
}
return best;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED