Burst Balloons
Problem Description
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 <= 3000 <= nums[i] <= 100
Solve it on LeetCode
Approaches
1. Dynamic Programming (Memoization)
Intuition:
The key observation in this problem is that the order of bursting balloons does not matter globally, but it matters locally for a particular subproblem. We can think of each balloon as contributing coins when it is the last balloon of any subsequence to be burst. We can use dynamic programming to solve this by dividing the problem into subproblems, where we consider bursting a balloon last in a specific range, and compute the maximum coins obtainable.
Let's use a dynamic programming table dp where dp[left][right] represents the maximum coins obtainable by bursting all the balloons between index left and right (exclusive).
Steps:
- Use an auxiliary array
numswith additional boundary balloons (values 1 at both ends), because the edge balloons behave as if they are surrounded by 1. - Use a helper function
maxCoins(left, right)which uses memoization to store already computed results. - For each balloon
ibetweenleftandright, calculate the coins gained by making it the last burst balloon, plus the resulting coins from the two partitions(left, i)and(i, right). - Memorize and return the maximum result for subproblem
maxCoins(left, right).
Code:
- Time Complexity: O(n^3) - We have two loops and each subproblem solution involves a linear work due to memoization.
- Space Complexity: O(n^2) - Due to the extra space for the memoization table.
2. Dynamic Programming (Tabulation)
Intuition:
This approach is similar to the memoization approach, but we fill up our table in a bottom-up manner instead. We compute the solution for smaller subproblems first and use them to build up the solution for larger subproblems.
Steps:
- We still prepare an auxiliary array
numswith boundary balloons. - Initialize a DP table where
dp[i][j]will represent the maximum coins obtainable by bursting all the balloons between indexiandj(exclusive). - Use a nested loop structure to compute
dp[i][j]for subproblems of increasing size. - For each
kin current subproblem, compute maximum coins by bursting thek-thballoon last in its section.
Code:
- Time Complexity: O(n^3) - Due to three nested loops over the length and boundaries.
- Space Complexity: O(n^2) - Due to the space needed for the DP table.