Burst Balloons

Master this topic with zero to advance depth.

Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it, represented by an array nums. You are asked to burst all the balloons.

If you burst the i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. After bursting it, the i - 1-th and i + 1-th balloons become adjacent.

Find the maximum coins you can collect by bursting the balloons wisely. (Assume nums[-1] = nums[n] = 1).

Visual Representation

nums = [3, 1, 5, 8]

Add boundary: [1, 3, 1, 5, 8, 1]

If we burst 1 first:
Coins = 3 * 1 * 5 = 15
Remaining: [1, 3, 5, 8, 1]

Wait! It's better to think: "Which balloon is burst LAST in range (i, j)?"

Hard

Examples

Input: nums = [3, 1, 5, 8]
Output: 167
nums = [3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> []
coins = 315 + 358 + 138 + 181 = 15 + 120 + 24 + 8 = 167

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

Approach 1

Level I: Brute Force (Recursion)

Intuition

Pick a balloon k to burst last in the interval (i, j). This splits the problem into two subproblems: bursting balloons in (i, k) and (k, j). Try all possible candidates for the last balloon.

Thought Process

Pad the array with 1 at both ends.
Define a function solve(i, j) that returns max coins from interval [i, j].
Base case: If i > j, return 0.
Recursive step: max(solve(i, k-1) + solve(k+1, j) + A[i-1]*A[k]*A[j+1]) for all k in [i, j].

⏱ Exponential💾 O(N) for recursion

Detailed Dry Run

nums=[3, 1, 5] -> A=[1, 3, 1, 5, 1] solve(1, 3) where length is 3. Try k=2 as last: solve(1, 1) + solve(3, 3) + 111 = 3 + 25 + 1 = 29.

java

public class Main {
    public static int solve(int[] A, int i, int j) {
        if (i > j) return 0;
        int max = 0;
        for (int k = i; k <= j; k++) {
            int coins = A[i - 1] * A[k] * A[j + 1] + solve(A, i, k - 1) + solve(A, k + 1, j);
            max = Math.max(max, coins);
        }
        return max;
    }

    public static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] A = new int[n + 2];
        A[0] = 1; A[n + 1] = 1;
        for (int i = 0; i < n; i++) A[i + 1] = nums[i];
        return solve(A, 1, n);
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

Approach 2

Level II: Memoization (Top-Down Interval DP)

Intuition

The brute force re-solves the same (i, j) intervals. We add a 2D memo table to cache the max coins for each interval.

Visual

nums=[3,1,5,8], A=[1,3,1,5,8,1]
memo[1][4] = max coins for range (1..4)
After first computation, reused whenever (1,4) is subproblem!

⏱ O(N^3)💾 O(N^2)

Detailed Dry Run

A=[1,3,1,5,8,1]. memo[1][4]: try k=1,2,3,4 as last balloon. k=3 gives 351+memo[1][2]+memo[4][4]=15+9+40=... Cached!

java

public class Main {
    static int[] A;
    static int[][] memo;
    public static int solve(int i, int j) {
        if (i > j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = 0;
        for (int k = i; k <= j; k++) {
            int coins = A[i - 1] * A[k] * A[j + 1] + solve(i, k - 1) + solve(k + 1, j);
            res = Math.max(res, coins);
        }
        return memo[i][j] = res;
    }

    public static int maxCoins(int[] nums) {
        int n = nums.length;
        A = new int[n + 2];
        A[0] = A[n + 1] = 1;
        for (int i = 0; i < n; i++) A[i + 1] = nums[i];
        memo = new int[n + 2][n + 2];
        for (int[] row : memo) java.util.Arrays.fill(row, -1);
        return solve(1, n);
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

⚠️ Common Pitfalls & Tips

This is an interval DP problem. The key insight — picking the LAST balloon to burst — allows clean decomposition. Memoization here gives the same O(N^3) as bottom-up but is easier to reason about.

Approach 3

Level III: Dynamic Programming (Interval/Matrix Chain)

Intuition

Instead of deciding which balloon to burst first, we decide which balloon k is burst last in the interval (i, j). This allows us to split the problem into two independent subproblems: bursting balloons in (i, k) and (k, j).

Thought Process

Pad the array with 1 at both ends.
dp[i][j] = max coins from bursting balloons between index i and j (exclusive).
For each length len from 1 to n:
- For each start i from 1 to n - len + 1:
  - End j = i + len - 1.
  - For k from i to j (last balloon to burst):
    - coins = nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j].

⏱ O(N^3)💾 O(N^2)

Detailed Dry Run

nums = [3, 1, 5] Boundary padded: [1, 3, 1, 5, 1]

Interval	Last k	Calculation	Result
(1,1)	1	131 + 0 + 0	3
(2,2)	2	315 + 0 + 0	15
(3,3)	3	551 + 0 + 0	25
(1,2)	1	135 + 0 + dp[2][2] = 15+15	30
(1,2)	2	115 + dp[1][1] + 0 = 5+3	8

java

public class Main {
    public static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] padded = new int[n + 2];
        padded[0] = 1; padded[n + 1] = 1;
        System.arraycopy(nums, 0, padded, 1, n);

        int[][] dp = new int[n + 2][n + 2];

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], 
                        padded[i - 1] * padded[k] * padded[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

⚠️ Common Pitfalls & Tips

The intuition for O(N^3) interval DP is often hard to find. Remember: "last item to be processed" is a common pattern for problems involving shrinking ranges (like Matrix Chain Multiplication).

← Previous QuestionRegular Expression Matching

Next Question →Longest Valid Parentheses

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.