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].
function burstBalloons(nums) {
let n = nums.length + 2;
nums = [1].concat(nums).concat([1]);
let dp = Array(n)
.fill(0)
.map(() => Array(n).fill(0));
for (let length = 1; length <= n - 1; length++) {
for (let left = 0; left <= n - length - 1; left++) {
let right = left + length - 1;
for (let i = left + 1; i <= right; i++) {
dp[left][right] = Math.max(
dp[left][right],
nums[left] * nums[i] * nums[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?
