NeetCode #741LC-312Hard2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems#741 · #312 · Burst Balloons(戳气球)
📌 Problem Statement & Constraints
Given
nums representing balloons, bursting balloon i yields nums[i-1] * nums[i] * nums[i+1] coins, where out-of-range neighbours count as 1. After bursting, the remaining balloons close the gap. Return the maximum coins from bursting all balloons. Constraints: 1 <= nums.length <= 300, 0 <= nums[i] <= 100.💡 Core Algorithmic Approaches
- Pad
numswith a leading and trailing 1 so boundary balloons have explicit neighbours. - Think about which balloon is burst last in an interval
(i, j); call itk. Then the interval splits into(i, k)and(k, j)independently. - This gives
dp[i][j] = max over i < k < j of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]. - Iterating intervals by increasing length ensures the subintervals are solved first.
💻 Benchmark Python3 Implementation
class Solution:
def maxCoins(self, nums: List[int]) -> int:
a = [1] + nums + [1] # virtual boundary balloons
n = len(a)
dp = [[0] * n for _ in range(n)]
for length in range(2, n): # interval width
for i in range(n - length):
j = i + length
for k in range(i + 1, j):
coins = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]
if coins > dp[i][j]:
dp[i][j] = coins
return dp[0][n - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^3): the interval DP tries every split point for every interval.
💾 Space Complexity
O(n^2): the DP table.
⚠️ Interview Pitfalls & Follow-ups
- Thinking about which balloon is burst first: only the last-burst framing keeps the two sides independent.
- Using
nums[i] * nums[k] * nums[j]without padding: boundary balloons would index out of range. - Iterating intervals by start index: the subintervals would not be ready; process by increasing length.
- Trying a greedy smallest-first rule: greedy is not optimal, as
[3, 1, 5]demonstrates.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.