Burst Balloons
Given a list of balloons, where each balloon has a value and a point value when burst, find the maximum points that can be obtained by bursting the balloons in a specific order.
Constraints:
- The input list of balloons is not empty
- The length of the input list is less than or equal to 100
- Each balloon has a unique value
Examples:
Input: [3, 1, 5, 8]
Output: 167
Explanation: The optimal order to burst the balloons is: 3, 1, 5, 8. The points obtained are: (3 * 1 * 5) + (1 * 3 * 8) + (5 * 3 * 8) + (8 * 1 * 5) = 167
Solutions
Dynamic Programming
Time: O(n^4)Space: O(n^2)
The dynamic programming approach involves creating a 2D array dp where dp[i][j] represents the maximum points that can be obtained by bursting the balloons in the range [i, j]. The final answer is stored in dp[0][n - 1].
int burstBalloons(vector<int>& nums) {
int n = nums.size() + 2;
vector<int> nums2(n);
nums2[0] = 1;
nums2[n - 1] = 1;
for (int i = 0;
i < nums.size();
i++) {
nums2[i + 1] = nums[i];
}
vector<vector<int>> dp(n, vector<int>(n));
for (int length = 1;
length <= n - 1;
length++) {
for (int left = 0;
left <= n - length - 1;
left++) {
int right = left + length - 1;
for (int i = left + 1;
i <= right;
i++) {
dp[left][right] = max(dp[left][right], nums2[left] * nums2[i] * nums2[right + 1] + dp[left][i - 1] + dp[i + 1][right]);
}
}
}
return dp[0][n - 1];
}Follow-up:
What if the balloons have different point values when burst in different orders?
