You are given an array of positive integers nums where each element represents a balloon. You can burst them one at a time. When you burst the i-th balloon, you gain coins equal to nums[i - 1] * nums[i] * nums[i + 1]. After the balloon is burst, it disappears and the adjacent balloons become neighbors. If i - 1 or i + 1 is out of bounds, treat the corresponding value as 1.
Your task is to return the maximum coins you can collect by bursting the balloons wisely.
Constraints:
nums.length ≤ 300nums[i] ≤ 100
At first glance, it might seem reasonable to try every possible order of bursting balloons and keep track of the maximum coins collected. However, the number of possible orders grows extremely fast (factorial time), making brute-force infeasible for even moderate input sizes.
The key insight is to realize that the value you get from bursting a balloon depends on its neighbors at the time it is burst. This means the coins earned from bursting a balloon changes as the array shrinks.
Instead of thinking about the order in which we burst balloons, we can think recursively: for any subarray of balloons, what's the best we can do if we assume the last balloon to be burst in that range? If we fix the last balloon to burst in a subarray, the subproblems to the left and right are independent, and we can use dynamic programming to store and reuse results for subproblems.
We'll use dynamic programming to solve this problem efficiently. Here's a step-by-step breakdown:
1 to both ends of the nums array. This simplifies boundary calculations, as bursting the first or last balloon always has a "neighbor" of value 1.
dp[left][right] represent the maximum coins we can collect by bursting all balloons between left and right (exclusive). Initially, dp is filled with 0s.
(left, right), consider all possible positions i where the last balloon is burst. The coins gained are:
left and i (exclusive): dp[left][i]i and right (exclusive): dp[i][right]i last: nums[left] * nums[i] * nums[right]dp[left][right] = max(dp[left][right], dp[left][i] + nums[left]*nums[i]*nums[right] + dp[i][right]) for all i in (left+1, right).
dp table for increasing subarray lengths, from 2 up to n+2 (due to padding).
dp[0][n+1], representing the maximum coins for the whole (padded) array.
This approach ensures that each subproblem is solved only once, and overlapping subproblems are reused, making it efficient even for large arrays.
Let's walk through an example with nums = [3, 1, 5, 8].
Step 1: Pad the array: nums = [1, 3, 1, 5, 8, 1].
Step 2: We'll build up dp[left][right] for all subarrays.
(1, 3) (i.e., [3,1]), possible last balloons to burst:
nums[0]*nums[1]*nums[3] = 1*3*5 = 15nums[1]*nums[2]*nums[3] = 3*1*5 = 15dp[1][3] = max(15, 15) = 15
(0, 5), we try bursting each balloon last in this range:
dp[0][1] + nums[0]*nums[1]*nums[5] + dp[1][5] = 0 + 1*3*1 + ...dp for all subproblems, and finally dp[0][5] = 167.
The maximum coins you can collect is 167.
Brute-force approach:
Trying all possible orders of bursting balloons is factorial in time: O(n!). This is computationally infeasible for n > 10.
Dynamic programming approach:
O(n^2) subproblems (all pairs of left and right), and for each subproblem, we try up to O(n) possible last balloons, so total is O(n^3).O(n^2).n up to 300.
The Burst Balloons problem is a classic example where a brute-force approach is impractical due to the huge number of possible orders. By reframing the problem to focus on the last balloon burst in a subarray, we can use dynamic programming to efficiently compute the maximum coins. Padding the array with 1s simplifies boundary cases, and the DP formulation ensures we solve each subproblem only once. This elegant approach turns a seemingly intractable problem into one that's solvable in cubic time.
class Solution:
def maxCoins(self, nums):
n = len(nums)
nums = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for length in range(2, n + 2):
for left in range(0, n + 2 - length):
right = left + length
for i in range(left + 1, right):
dp[left][right] = max(
dp[left][right],
dp[left][i] + nums[left]*nums[i]*nums[right] + dp[i][right]
)
return dp[0][n + 1]
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> arr(n + 2, 1);
for (int i = 0; i < n; ++i) arr[i + 1] = nums[i];
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int len = 2; len <= n + 1; ++len) {
for (int left = 0; left + len <= n + 1; ++left) {
int right = left + len;
for (int i = left + 1; i < right; ++i) {
dp[left][right] = max(
dp[left][right],
dp[left][i] + arr[left] * arr[i] * arr[right] + dp[i][right]
);
}
}
}
return dp[0][n + 1];
}
};
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
int[][] dp = new int[n + 2][n + 2];
for (int len = 2; len <= n + 1; len++) {
for (int left = 0; left + len <= n + 1; left++) {
int right = left + len;
for (int i = left + 1; i < right; i++) {
dp[left][right] = Math.max(
dp[left][right],
dp[left][i] + arr[left] * arr[i] * arr[right] + dp[i][right]
);
}
}
}
return dp[0][n + 1];
}
}
var maxCoins = function(nums) {
const n = nums.length;
const arr = [1, ...nums, 1];
const dp = Array.from({length: n + 2}, () => Array(n + 2).fill(0));
for (let len = 2; len <= n + 1; len++) {
for (let left = 0; left + len <= n + 1; left++) {
const right = left + len;
for (let i = left + 1; i < right; i++) {
dp[left][right] = Math.max(
dp[left][right],
dp[left][i] + arr[left] * arr[i] * arr[right] + dp[i][right]
);
}
}
}
return dp[0][n + 1];
};