Daily DSA: Burst Balloons (Hard)
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 i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. After the burst, the (i - 1)-th and (i + 1)-th then become adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
- You may imagine
nums[-1] = nums[n] = 1. They are not real, therefore you cannot burst them. 0 <= n <= 3000 <= nums[i] <= 100
Examples
Example 1:
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation:
nums = [3, 1, 5, 8] --> [3, 5, 8] --> [3, 8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.
Example 2:
Input: nums = [1, 5]
Output: 10
Explanation:
nums = [1, 5] --> [5] --> []
coins = 1*1*5 + 1*5*1 = 10.
Constraints
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Approach
This problem can be solved using Interval Dynamic Programming.
If we try to simulate bursting balloons from first to last, the subproblems become dependent on which balloons were burst previously, because the neighbors of a balloon change. However, if we think in reverse—which balloon is the last one to burst in a given range—the subproblems become independent.
- Define the DP State: Let
dp[i][j]be the maximum coins we can collect by bursting all balloons in the open interval(i, j). The balloons at indicesiandjare not burst; they act as boundaries. - Base Case: If
j <= i + 1, there are no balloons to burst betweeniandj, sodp[i][j] = 0. - Transitions: To calculate
dp[i][j], we iterate through every possible balloonkthat could be the last one to burst in the interval(i, j).- If
kis the last balloon to burst in(i, j), then all balloons in(i, k)and(k, j)must have already been burst. - The coins gained from bursting
klast will benums[i] * nums[k] * nums[j]. - Therefore:
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])for alli < k < j.
- If
- Final Answer: The answer will be
dp[0][n+1]after padding the original array with1at both ends.
Complexity Analysis
- Time Complexity: $O(N^3)$, where $N$ is the number of balloons. There are $O(N^2)$ states, and each state takes $O(N)$ to compute.
- Space Complexity: $O(N^2)$ to store the DP table.
C++ Solution
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
// Pad the array with 1s at the boundaries
vector<int> vals(n + 2);
vals[0] = 1;
vals[n + 1] = 1;
for (int i = 0; i < n; ++i) {
vals[i + 1] = nums[i];
}
// dp[i][j] means max coins for bursting balloons in open interval (i, j)
int m = n + 2;
vector<vector<int>> dp(m, vector<int>(m, 0));
// len is the length of the interval (j - i)
for (int len = 2; len < m; ++len) {
for (int i = 0; i < m - len; ++i) {
int j = i + len;
// Try each balloon k in (i, j) as the last one to burst
for (int k = i + 1; k < j; ++k) {
int current_coins = vals[i] * vals[k] * vals[j];
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + current_coins);
}
}
}
return dp[0][m - 1];
}
};