Problem 32.4 · Advanced DPHard

Burst Balloons

What it teaches: Interval DP with the "last one to burst" choice.

Practise it on judges as “Burst Balloons”.

The problem

Bursting balloon i earns nums[left] × nums[i] × nums[right] using its current neighbours (missing neighbours count as 1). Return the maximum coins for bursting all balloons.

Example 1

Input: nums = [3, 1, 5, 8]
Output: 167

Constraints

1 ≤ n ≤ 300

Pattern clues in the wording

→ Removing items changes neighbours
→ Small n (O(n³) ok)

These clues point to Interval DP: dp[i][j] is the answer for the range i..j, built from smaller ranges by trying every split point.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxCoins(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [3,1,5,8]	167
2	nums = [1,5]	10

From slow to fast

Approaches

1. Interval DP · O(n³)

Interval DP

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

a = [1] + nums + [1]. For gap = 2.. length, dp[l][r] = max over l < k < r of dp[l][k] + dp[k][r] + a[l] a[k] a[r].

Approach 1

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length + 2;
        int[] a = new int[n];
        a[0] = a[n - 1] = 1;
        for (int i = 0; i < nums.length; i++) a[i + 1] = nums[i];
        int[][] dp = new int[n][n];
        for (int gap = 2; gap < n; gap++)
            for (int l = 0; l + gap < n; l++) {
                int r = l + gap;
                for (int k = l + 1; k < r; k++)
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
            }
        return dp[0][n - 1];
    }
}

Verdict: The canonical interval DP.

Before you submit

Edge cases and common mistakes

Test these inputs

One balloon
Zeros

Mistakes people make

Choosing the first balloon to burst (subproblems aren't independent).

Interview

Follow-up questions

What other problems use "the last operation"?

Command Palette

The problem

Approaches

Interval DP

Edge cases and common mistakes

Follow-up questions