Burst Balloons — Hard Problem & Solution

Problem statement

Balloon i is painted with the number nums[i]. Bursting balloon i earns nums[i-1] · nums[i] · nums[i+1] coins, where an out-of-range neighbour counts as 1. After a burst, its neighbours become adjacent.

Burst all the balloons and return the maximum coins you can collect.

Example 1

Input: nums = [3,1,5,8]
Output: 167
Explanation: Burst 1, then 5, then 3, then 8.

Example 2

Input: nums = [1,5]
Output: 10

Example 3

Input: nums = [7]
Output: 7

Constraints

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

How to solve Burst Balloons

Interval DP on 'last to burst'. If balloon k is the last one popped inside [i, j], then at that moment its neighbours are exactly a[i-1] and a[j+1], which are outside the range and therefore fixed — that is what makes the subproblems independent.

Approach

1. Pad: a = [1] + nums + [1].
2. Let dp[i][j] be the best coins from bursting everything strictly inside [i, j].
3. Try each k in [i, j] as the last burst: dp[i][k-1] + a[i-1]·a[k]·a[j+1] + dp[k+1][j].
4. Fill by increasing interval length; the answer is dp[1][n].

Why it works

Choosing the first burst leaves two sides that are no longer independent — the surviving balloons can interact across the gap. Choosing the last burst inside a range fixes that balloon's neighbours to the range's outside boundaries, so the left and right sub-ranges never influence each other and their optima simply add.

Complexity

• Time — O(n³)
• Space — O(n²)

Pitfalls

• Recursing on 'first to burst' gives overlapping, non-independent subproblems and a wrong answer.
• The multiplication uses the range boundaries a[i-1] and a[j+1], not a[k-1] and a[k+1].
• The padding is what makes the edge cases uniform; without it the boundaries need special handling.

Reference solution

Python

from typing import List

def maxCoins(nums: List[int]) -> int:
    n = len(nums)
    a = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(1, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            for k in range(i, j + 1):
                dp[i][j] = max(dp[i][j], dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j])
    return dp[1][n]

JavaScript

var maxCoins = function(nums) {
    var n = nums.length;
    var a = [1].concat(nums).concat([1]);
    var dp = [];
    for (var p = 0; p < n + 2; p++) {
        var row = [];
        for (var q = 0; q < n + 2; q++) row.push(0);
        dp.push(row);
    }
    for (var len = 1; len <= n; len++) {
        for (var i = 1; i + len - 1 <= n; i++) {
            var j = i + len - 1;
            for (var k = i; k <= j; k++) {
                var val = dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j];
                if (val > dp[i][j]) dp[i][j] = val;
            }
        }
    }
    return dp[1][n];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard