burst-balloons-max-coins

Answer

This is the classic Burst Balloons interval-DP problem. The key insight: instead of reasoning about which balloon to pop first (which makes the "nearest alive neighbor" hard to track), think about which balloon in an interval is popped last. If balloon k is the last one popped inside the open interval (i, j), then when it pops, balloons i and j are the only survivors bordering it — regardless of the order everything inside was popped. Its contribution is exactly nums[i] * nums[k] * nums[j], and the left/right subproblems (i, k) and (k, j) are independent.

So pad the array with boundary sentinels 1 on both ends and define:

dp[i][j] = max coins from popping all balloons strictly inside (i, j),
           given balloons i and j are still alive (never popped within this interval)
dp[i][j] = max over k in (i+1 .. j-1) of  dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
answer   = dp[0][n+1]

This is O(n³) time and O(n²) memory, comfortably handling n = 500 (~21M inner-loop iterations, runs in ~2s in CPython).

def maxCoins(nums):
    n = len(nums)
    if n == 0:
        return 0
    padded = [1] + nums + [1]          # sentinels
    N = n + 2
    dp = [[0] * N for _ in range(N)]

    for length in range(2, N):         # interval width (j - i)
        for i in range(N - length):
            j = i + length
            vi, vj = padded[i], padded[j]
            best = 0
            # k is the LAST balloon popped inside (i, j)
            for k in range(i + 1, j):
                val = dp[i][k] + dp[k][j] + vi * padded[k] * vj
                if val > best:
                    best = val
            dp[i][j] = best

    return dp[0][N - 1]

Why it works: whichever balloon k pops last in (i, j), everything to its left was fully cleared (cost dp[i][k]), everything to its right was fully cleared (cost dp[k][j]), and at that final moment its neighbors are exactly i and j (sentinels guaranteed alive), so the award is nums[i]·nums[k]·nums[j]. Trying every k and taking the max enumerates all possible last-popped choices, hence all orders.