Topics › Dynamic Programming › MCM DP - Partition DP

Burst balloons

Hard TUF ID 326 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

There are n balloons in a row, balloon i painted with the number nums[i]. You burst them one at a time, in any order. Bursting balloon i earns left · nums[i] · right coins, where left and right are the numbers on the balloons currently adjacent to it (already-burst balloons are gone, so neighbours change over time). If there is no balloon on a side, that side counts as 1. Return the maximum total number of coins.

Constraints (LeetCode 312): 1 ≤ n ≤ 300, 0 ≤ nums[i] ≤ 100. The Java methods also accept an empty array (answer 0).

Example 1

nums = [3, 1, 5, 8]
answer = 167
// burst 1: 3·1·5 = 15   -> [3, 5, 8]
// burst 5: 3·5·8 = 120  -> [3, 8]
// burst 3: 1·3·8 = 24   -> [8]
// burst 8: 1·8·1 = 8    -> []

Example 2

nums = [1, 5]
answer = 10      // burst 1 (1·1·5 = 5), then 5 (1·5·1 = 5)

Approach 1: Brute force

Intuition. Try every order. At each step pick any remaining balloon, earn its coins with its current neighbours, remove it, and recurse on what is left. Undo the removal afterwards so the next choice starts from the same list.

Algorithm.

1. For each index i of the current list, compute left · x · right using 1 beyond the ends.
2. Remove the balloon, add the best result of the remaining list, put the balloon back.
3. Return the best over all i.

static int bruteForce(int[] nums) {
    List<Integer> list = new ArrayList<>();
    for (int x : nums) list.add(x);
    return tryAll(list);
}

static int tryAll(List<Integer> list) {
    int best = 0;
    for (int i = 0; i < list.size(); i++) {
        int left = i > 0 ? list.get(i - 1) : 1;
        int right = i < list.size() - 1 ? list.get(i + 1) : 1;
        int x = list.remove(i);
        best = Math.max(best, left * x * right + tryAll(list));
        list.add(i, x);                                     // undo before trying the next balloon
    }
    return best;
}

Complexity. Time O(n! · n): n! orders, each step paying O(n) for list removal. Space O(n).

Why “burst first” does not split, and “burst last” does

The natural partition idea is: pick the balloon k to burst first, then solve the left part and the right part separately. That fails. After k is gone, the balloons k - 1 and k + 1 become neighbours, so a burst on the left side can earn coins from a balloon on the right side. The two halves are coupled.

Turn the question around: pick the balloon k that is burst last among those strictly between two walls i and j. While k is still standing, it separates the row: nothing left of k can ever be adjacent to anything right of k. So the balloons in (i, k) are burst with walls i and k, the balloons in (k, j) with walls k and j, independently. When k finally bursts, everything between the walls is gone, so its neighbours are exactly i and j, and it earns a[i] · a[k] · a[j].

To give the outermost balloons walls as well, pad the array: a = [1, nums..., 1]. The two padded 1s are never burst; they play the role of “no balloon, counts as 1”. With that,

f(i, j) = 0                                        if j - i < 2   (no balloon strictly inside)
f(i, j) = max over i < k < j of  f(i, k) + f(k, j) + a[i] · a[k] · a[j]
answer  = f(0, n + 1)

Approach 2: Recursion

Intuition. Implement the recurrence. solve(i, j) returns the best coins for the balloons strictly between walls i and j.

Algorithm.

1. Build the padded array.
2. If no balloon lies between i and j, return 0.
3. Otherwise try every k in between as the last balloon and keep the best.

static int[] padded(int[] nums) {
    int[] a = new int[nums.length + 2];
    a[0] = 1;
    a[a.length - 1] = 1;
    System.arraycopy(nums, 0, a, 1, nums.length);
    return a;
}

static int recursive(int[] nums) {
    int[] a = padded(nums);
    return solve(0, a.length - 1, a);
}

static int solve(int i, int j, int[] a) {
    if (j - i < 2) return 0;                                // no balloon strictly between i and j
    int best = 0;
    for (int k = i + 1; k < j; k++) {                       // k is the last balloon left between i and j
        best = Math.max(best, solve(i, k, a) + solve(k, j, a) + a[i] * a[k] * a[j]);
    }
    return best;
}

Complexity. Exponential time, though far smaller than n!, because the recursion now enumerates split trees instead of orders. Space O(n) for the depth.

Approach 3: Memoization

Intuition. There are only O(n^2) windows (i, j), and the recursion asks for the same ones many times. Cache each in dp[i][j]. Coins are never negative, so -1 means “not computed”.

Algorithm.

1. Pad the array and fill dp with -1.
2. Return the cached window when present; otherwise compute, store and return it.

static int memoization(int[] nums) {
    int[] a = padded(nums);
    int[][] dp = new int[a.length][a.length];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, a.length - 1, a, dp);
}

static int memo(int i, int j, int[] a, int[][] dp) {
    if (j - i < 2) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int best = 0;
    for (int k = i + 1; k < j; k++) {
        best = Math.max(best, memo(i, k, a, dp) + memo(k, j, a, dp) + a[i] * a[k] * a[j]);
    }
    return dp[i][j] = best;
}

Complexity. Time O(n^3): O(n^2) windows, each trying O(n) last balloons. For n = 300 that is about 4.5 million inner steps. Space O(n^2).

Approach 4: Tabulation

Intuition. dp[i][j] reads dp[i][k] (same row, to the left) and dp[k][j] (a lower row). Fill i from the bottom up and j from left to right. Windows with j = i + 1 contain no balloon and stay 0.

Algorithm.

1. Pad the array to length m = n + 2; allocate dp[m][m].
2. For i from m - 3 down to 0, for j from i + 2 to m - 1: maximise over k.
3. Return dp[0][m - 1].

static int tabulation(int[] nums) {
    int[] a = padded(nums);
    int m = a.length;
    int[][] dp = new int[m][m];                             // dp[i][i + 1] = 0: empty window
    for (int i = m - 3; i >= 0; i--) {
        for (int j = i + 2; j < m; j++) {
            int best = 0;
            for (int k = i + 1; k < j; k++) best = Math.max(best, dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            dp[i][j] = best;
        }
    }
    return dp[0][m - 1];
}

Dry run on Example 1: a = [1, 3, 1, 5, 8, 1] (indices 0 to 5). Some smaller windows first:

The full window dp[0][5] tries each balloon as the last one:

So 8 is burst last, matching the order shown in the example.

Complexity. Time O(n^3), space O(n^2).

Edge cases and pitfalls

• Thinking forwards. Any recurrence based on the first balloon burst is wrong because the halves share neighbours afterwards. The “last balloon” view is the whole trick.
• The walls are not balloons. k ranges strictly between i and j; the padded 1s are never burst.
• Zeros. A balloon with 0 earns nothing and zeroes out its neighbours’ products. [2, 0, 3] is best handled by bursting 0 first (0 coins), then 2 with neighbours 1 and 3 (6), then 3 (3): total 9.
• Single balloon. It earns 1 · x · 1 = x.
• Overflow. At most 300 bursts of at most 100^3 = 10^6 coins each stays under 3 × 10^8, so int is safe.
• Testing. The brute force is only run for n ≤ 7; 150 seeded random arrays compare all four methods, and a 300-balloon array checks that memoization and tabulation agree on a full-size input.

Related problems

• Matrix chain multiplication also reasons about the last operation on a range.
• Matrix Chain Multiplication - Bottom-Up - (DP-49) explains the fill order of interval tables.
• Minimum cost to cut the stick uses the same padding with sentinel ends, but there the first cut splits cleanly.
• Different Ways to Evaluate a Boolean Expression is another interval DP over a split point.
• Partition Array for Maximum Sum is a simpler, one-dimensional partition DP.