Burst Balloons

Intuition

Deciding which balloon to burst first is hard because it changes everyone's neighbors, so instead we reason about which balloon is burst last inside an interval. If balloon k is the last one popped in the open range (l, r), then when it pops its only surviving neighbors are the fixed boundaries l and r, earning nums[l] * nums[k] * nums[r]. Everything to the left of k and everything to the right of k are solved independently as smaller subproblems dp[l][k] and dp[k][r]. Padding nums with a 1 on both ends removes the special-casing for edge balloons. We fill the table by increasing interval length so both halves are ready when we combine them.

Algorithm walkthrough

1. 1Build balloons = [1] + nums + [1] so index 0 and the last index act as boundary walls of value 1.
2. 2Let dp[l][r] hold the maximum coins obtainable strictly between boundaries l and r (both exclusive).
3. 3Iterate interval lengths from 2 upward; for each length choose the left boundary l and set r = l + length.
4. 4For every k in (l, r), treat k as the last balloon popped: gain balloons[l]*balloons[k]*balloons[r] plus dp[l][k] and dp[k][r].
5. 5Keep the maximum over all k in dp[l][r], and finally return dp[0][n-1] spanning the full padded array.

Implementation

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        balloons = [1] + nums + [1]
        n = len(balloons)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for l in range(0, n - length):
                r = l + length
                for k in range(l + 1, r):
                    coins = balloons[l] * balloons[k] * balloons[r]
                    dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + coins)
        return dp[0][n - 1]