Official 162 views

Editorial: Burst Balloons

by admin · Oct. 18, 2026

1 Intuition

Think about which balloon in an interval is burst **last** — its neighbours are then the interval's walls.

2 Approach

Pad with 1s. dp[lo][hi] = best coins from balloons strictly between lo and hi = max over k of dp[lo][k] + a[lo]·a[k]·a[hi] + dp[k][hi].

3 Complexity Analysis

Time O(n³), Space O(n²).

4 Solution Code

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        a = [1] + nums + [1]
        n = len(a)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for lo in range(n - length):
                hi = lo + length
                for k in range(lo + 1, hi):
                    dp[lo][hi] = max(dp[lo][hi], dp[lo][k] + a[lo] * a[k] * a[hi] + dp[k][hi])
        return dp[0][n - 1]

5 Code Walkthrough

The reference solution below implements the approach step by step.