Burst Balloons
Problem
Given an array of integers nums representing balloons, return the maximum coins you can collect by bursting all the balloons wisely, where bursting balloon i yields coins equal to nums[left] * nums[i] * nums[right], with left and right being adjacent balloons after previous bursts.
- 1 ≤ nums.length ≤ 300
- 0 ≤ nums[i] ≤ 100
Example
nums = [3,1,5,8]167A brute-force approach would try all permutations of bursting balloons, which is O(n!) and infeasible. Instead, the algorithm pads nums with 1s at both ends to handle boundaries uniformly. It then uses a recursive DP function dp(l, r) that computes the maximum coins obtainable by bursting all balloons in the range [l, r]. The key insight is to consider which balloon i in [l, r] to burst last. Bursting balloon i last means its neighbors are fixed as nums[l-1] and nums[r+1], so the coins gained are nums[l-1] * nums[i] * nums[r+1]. The problem then splits into two independent subproblems: bursting balloons in [l, i-1] and [i+1, r]. The algorithm tries all i in [l, r], memoizes results, and returns the maximum total coins.
Approach
Straightforward Solution
A brute-force approach tries all permutations of bursting balloons, resulting in O(n!) time complexity, which is computationally impossible for even moderate n.
Core Observation
The coins gained from bursting a balloon depend on its neighbors, which change dynamically as balloons are burst. This dependency makes naive approaches fail because subproblems are not independent if we pick the first balloon to burst. However, if we pick the last balloon to burst in a range, its neighbors are fixed, making subproblems independent and solvable via DP.
Path to Optimal
The key recognition signals are 'maximum coins' and 'dependent neighbors' which indicate Dynamic Programming with interval partitioning. The breakthrough is reversing the problem: instead of choosing the first balloon to burst, choose the last balloon to burst in a given range. This fixes the neighbors and splits the problem into two independent subproblems, enabling memoization and polynomial time complexity.
Optimal Approach
Use a top-down recursive DP function dp(l, r) that returns the maximum coins from bursting all balloons in the range [l, r]. For each i in [l, r], consider bursting balloon i last, gaining coins nums[l-1] * nums[i] * nums[r+1] plus the results of dp(l, i-1) and dp(i+1, r). Memoize results to avoid recomputation. The final answer is dp(1, n) after padding nums with 1s at both ends.
Time
O(n^3)
There are O(n^2) subproblems defined by intervals (l, r). For each subproblem, the algorithm tries up to O(n) choices for the last balloon to burst, resulting in O(n^3) total time.
Space
O(n^2)
The memoization dictionary stores results for each of the O(n^2) intervals. The recursion stack depth is O(n), but the dominant space is the memo cache.
Pattern Spotlight
Dynamic Programming (Interval DP)
When subproblems depend on dynamic neighbors, reverse the perspective to pick the last action in a range, fixing boundaries and creating independent subproblems suitable for DP.
Solution
| 1 | class Solution:
|
| 2 | def maxCoins(self, nums: list[int]) -> int:
|
| 3 | nums = [1] + nums + [1]
|
| 4 | memo = {}
|
| 5 |
|
| 6 | def dp(l, r):
|
| 7 | if l > r:
|
| 8 | return 0
|
| 9 | if (l, r) in memo:
|
| 10 | return memo[(l, r)]
|
| 11 |
|
| 12 | max_coins = 0
|
| 13 | for i in range(l, r + 1):
|
| 14 | coins = nums[l - 1] * nums[i] * nums[r + 1]
|
| 15 | coins += dp(l, i - 1) + dp(i + 1, r)
|
| 16 | max_coins = max(max_coins, coins)
|
| 17 |
|
| 18 | memo[(l, r)] = max_coins
|
| 19 | return max_coins
|
| 20 |
|
| 21 | return dp(1, len(nums) - 2) |
Step-by-Step Solution
Pad Input and Initialize Memoization Cache
| 3 | nums = [1] + nums + [1]
|
| 4 | memo = {}
|
Objective
To simplify boundary handling by padding the input array with virtual balloons and prepare a cache for memoization.
Key Insight
Padding nums with 1 at both ends ensures that every balloon has fixed neighbors during the DP calculation, eliminating edge-case checks. The memo dictionary caches results for intervals to avoid redundant computations, transforming exponential recursion into polynomial DP.
Interview Quick-Check
Core Logic
Padding with 1s creates fixed boundaries that simplify the DP recurrence by ensuring neighbors are always defined.
Common Pitfalls & Bugs
Forgetting to pad the array leads to complicated boundary checks and potential off-by-one errors.
Recursively Compute Maximum Coins for Subranges
| 6 | def dp(l, r):
|
| 7 | if l > r:
|
| 8 | return 0
|
| 9 | if (l, r) in memo:
|
| 10 | return memo[(l, r)]
|
| 12 | max_coins = 0
|
| 13 | for i in range(l, r + 1):
|
| 14 | coins = nums[l - 1] * nums[i] * nums[r + 1]
|
| 15 | coins += dp(l, i - 1) + dp(i + 1, r)
|
| 16 | max_coins = max(max_coins, coins)
|
| 18 | memo[(l, r)] = max_coins
|
| 19 | return max_coins
|
Objective
To recursively compute and memoize the maximum coins obtainable by bursting all balloons in the interval [l, r].
Key Insight
The DP function explores all possible balloons to burst last in the current range. For each candidate balloon i, it calculates coins gained from bursting i last plus the maximum coins from bursting left and right subranges independently. Memoization ensures each subproblem is solved once, enabling efficient reuse of results and pruning of the exponential search space.
Interview Quick-Check
Core Logic
The DP recurrence tries every balloon i in [l, r] as the last to burst, summing coins from bursting i last and the optimal solutions of the left and right subranges.
State & Boundaries
The base case returns 0 when l > r, representing an empty range with no balloons to burst.
Common Pitfalls & Bugs
Failing to memoize results leads to exponential time complexity due to repeated subproblem computations.
Complexity
Memoization reduces the time complexity from factorial to cubic by caching results for each interval.
Return Final Maximum Coins for Full Range
| 21 | return dp(1, len(nums) - 2) |
Objective
To initiate the DP recursion on the full range of original balloons and return the maximum coins achievable.
Key Insight
After padding, the original balloons correspond to indices 1 through len(nums)-2. Calling dp(1, len(nums)-2) triggers the recursive exploration of all subproblems, culminating in the maximum coins for bursting all balloons. This single call encapsulates the entire problem solution.
Interview Quick-Check
Core Logic
Starting the recursion on the full range ensures the solution considers all balloons and their optimal bursting order.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
return 0Check if the result for interval (l, r) is already memoized.
This lookup avoids recomputing subproblems, ensuring each interval is solved once and results are reused, critical for efficiency.
coins = nums[l - 1] * nums[i] * nums[r + 1]Calculate coins gained by bursting balloon i last, using fixed neighbors nums[l-1] and nums[r+1].
Because balloon i is last in [l, r], its neighbors are fixed as nums[l-1] and nums[r+1], allowing a direct calculation of coins gained without ambiguity.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
Memoization prevents redundant computations by storing the maximum coins for each interval, transforming an exponential recursion into polynomial time.
if (l, r) in memo:Return the cached result for interval (l, r) if available.
Returning memoized results prunes the recursion tree, preventing exponential blowup and enabling polynomial time complexity.
for i in range(l, r + 1):Iterate over all balloons i in the interval [l, r] as candidates for last burst.
Trying every balloon as the last to burst ensures the algorithm explores all possible bursting orders, guaranteeing the optimal solution.
coins += dp(l, i - 1) + dp(i + 1, r)Add coins from recursively bursting left and right subranges around i.
The problem splits into two independent subproblems: bursting balloons in [l, i-1] and [i+1, r], whose maximum coins can be summed due to independence guaranteed by last burst choice.
nums = [1] + nums + [1]Pad the input array nums with 1 at both ends to handle boundaries uniformly.
Padding with 1s creates fixed virtual balloons at the boundaries, ensuring that every balloon has defined neighbors during bursting, which simplifies the DP recurrence and eliminates edge-case handling.
if l > r:Return 0 if the current interval is empty (l > r).
An empty interval means no balloons to burst, so the maximum coins obtainable is zero, serving as the base case for recursion.
max_coins = max(max_coins, coins)Update max_coins with the maximum coins found so far.
This max operation selects the best last balloon to burst, embodying the principle of optimal substructure in DP.
memo[(l, r)] = max_coinsMemoize the maximum coins for interval (l, r).
Caching the result ensures that future calls with the same interval return instantly, preventing redundant computation and exponential blowup.
return dp(1, len(nums) - 2)Invoke dp on the full range of original balloons and return the result.
Starting the recursion on the full interval [1, len(nums)-2] after padding triggers the entire DP computation, yielding the maximum coins for bursting all balloons.
def dp(l, r):Define the recursive DP function dp(l, r) to compute max coins for bursting balloons in [l, r].
This function encapsulates the interval DP logic, representing the problem as subproblems over ranges of balloons, enabling divide-and-conquer with memoization.
max_coins = 0Initialize max_coins to track the best coins for the current interval.
This accumulator stores the maximum coins found by trying all possible last balloons to burst in the interval.
return max_coinsReturn the maximum coins for interval (l, r).
This returns the computed optimal solution for the subproblem, enabling the recursive build-up of the final answer.
Test Your Understanding
Why does choosing the last balloon to burst in a range create independent subproblems, whereas choosing the first does not?
Choosing the last balloon to burst fixes its neighbors as the boundaries of the range, making the left and right subranges independent because their balloons do not affect each other's neighbors. Choosing the first balloon to burst leaves neighbors undefined and interdependent, preventing independent subproblem solutions.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Burst Balloons from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Burst Balloons drill