⚡Flashcard Drill➔
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

  1. Pad nums with a leading and trailing 1 so boundary balloons have explicit neighbours.
  2. Think about which balloon is burst last in an interval (i, j); call it k. Then the interval splits into (i, k) and (k, j) independently.
  3. This gives dp[i][j] = max over i < k < j of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j].
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems