0312. 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 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 with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
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
Constraints:
n == nums.length1 <= n <= 5000 <= nums[i] <= 100
Analysis¶
This is a "Interval DP" problem, which means you need to create a 2-d array represent the optimal solution for each interval from start to end. Using dp[start][end] to represent the maximum value.
So for this problem, if nums = [3,1,5,8], then dp[1][4] is our solution.
Note
We use 1-based index for easy representation, because the boundary case: burst first balloon or last ballon is easier to be calculated. We just need to add two 1s to the beginning and the ending.
Next, we just need to try all the smaller segaments first then calculate the final answer.
First, we determine the length of each segament, and we start from len = 1, which means there is only one ballon, and ends at len = n
Second, we determine the starting and ending points. We use i to represent start and j to represent the end. Thus the range for start is from 1 to n-len+1, since we need to leave room for ending. If we have determined our i, then our ending point is fixed, which is i+len-1.
Finally, we need to determine which ballon to be bursted from the i to j range. We use k to represent the bursting point, and we try all the possible point from k = i to k=j.
- Time: O(n^3)
- Space: O(n^2) for the extra
dp2-d array
Code¶
class Solution {
public:
int maxCoins(vector<int> &nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> dp(n + 2, 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] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] +
dp[i][k - 1] + dp[k + 1][j]);
}
}
}
return dp[1][n];
}
};