Burst Balloons

Problem Description

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 ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon painted with a 1 number on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Examples

Constraints

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

Think Backwards: Select the Last Balloon to Burst

If we think forwards (which balloon to burst first), the array splits and adjacent elements change, making it difficult to define independent subproblems.

Instead, we think backwards: which balloon is the last to burst in the interval [i..j]?

• If balloon k (where i ≤ k ≤ j) is the last balloon to burst in the interval:
  • All other balloons in [i..k-1] and [k+1..j] have already been burst.
  • Therefore, the balloons adjacent to k when it is burst will be the boundaries of the interval: nums[i - 1] and nums[j + 1].
  • The coins obtained from bursting k last is: nums[i - 1] * nums[k] * nums[j + 1].
  • The total coins for the interval [i..j] is: dp[i][j] = max(dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]) for all k in [i..j].

To handle boundary conditions cleanly, we pad the input array with 1 at the beginning and the end.

Solution: Interval DP (O(N³))

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // Pad the array with 1 at both ends
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        System.arraycopy(nums, 0, arr, 1, n);

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

        // len is the length of the interval of balloons we are bursting
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                // k is the last balloon to burst in interval [i..j]
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j],
                        dp[i][k - 1] + arr[i - 1] * arr[k] * arr[j + 1] + dp[k + 1][j]
                    );
                }
            }
        }

        return dp[1][n];
    }
}

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        # Pad array with 1 at both ends
        arr = [1] + nums + [1]
        n = len(nums)
        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] + arr[i - 1] * arr[k] * arr[j + 1] + dp[k + 1][j]
                    )

        return dp[1][n]

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxCoins(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> arr(n + 2, 1);
        for (int i = 0; i < n; i++) {
            arr[i + 1] = nums[i];
        }

        std::vector<std::vector<int>> dp(n + 2, std::vector<int>(n + 2, 0));

        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] = std::max(dp[i][j],
                        dp[i][k - 1] + arr[i - 1] * arr[k] * arr[j + 1] + dp[k + 1][j]
                    );
                }
            }
        }

        return dp[1][n];
    }
};

Complexity Analysis:

• Time Complexity: O(N³) where N is the number of balloons. There are N² intervals, and we iterate over all possible last-burst balloons k in each interval. Given N ≤ 300, this executes about 2.7 * 10⁷ operations in the worst case, running in under 50ms in C++/Java.
• Space Complexity: O(N²) to store the DP table.

← All Problems