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].
def burst_balloons(nums):
n = len(nums) + 2; nums = [1] + nums + [1]; dp = [[0] * n for _ in range(n)]; for length in range(1, n - 1 + 1):
for left in range(n - length - 1 + 1):
right = left + length - 1; for i in range(left + 1, right + 1):
dp[left][right] = 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?
