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].
public int burstBalloons(int[] nums) {
int n = nums.length + 2;
int[] nums2 = new int[n];
nums2[0] = 1;
nums2[n - 1] = 1;
for (int i = 0;
i < nums.length;
i++) {
nums2[i + 1] = nums[i];
}
int[][] dp = new int[n][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] = Math.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?
