Burst Balloons
Problem Statement
You are given an array of integers nums
of size n
. The ith
element represents a balloon with an integer value of nums[i]
. You must burst all of the balloons.
If you burst the ith
balloon, you will receive nums[i - 1] * nums[i] * nums[i + 1]
coins. If i - 1
or i + 1
goes out of bounds of the array, then assume the out of bounds value is 1.
Return the maximum number of coins you can receive by bursting all of the balloons.
Example 1:
# Input: nums = [4,2,3,7]# Output: 167## Explanation:# nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []# coins = 4*2*3 + 4*3*7 + 1*4*7 + 1*7*1 = 143
Constraints:
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
Recommended Time and Space Complexity
Aim for a solution with O(n^3)
time complexity and O(n^2)
space complexity, where n
is the length of the input array.
Hint 1
Consider adding padding of 1 to the beginning and end of the array.
Hint 2
Think about how you could use dynamic programming to store and reuse intermediate results. Specifically, try to solve it bottom-up, determining the maximum coins attainable on smaller subproblems first.
Solution
Brute Force (Recursion)
def max_coins_brute_force(nums: List[int]) -> int: nums = [1] + nums + [1]
def dfs(nums): if len(nums) == 2: return 0
max_coins = 0 for i in range(1, len(nums) - 1): coins = nums[i - 1] * nums[i] * nums[i + 1] coins += dfs(nums[:i] + nums[i + 1:]) max_coins = max(max_coins, coins) return max_coins
return dfs(nums)
Time complexity: O(n*2^n)
Space complexity: O(n*2^n)
Dynamic Programming (Top-Down)
def max_coins_top_down(nums: List[int]) -> int: nums = [1] + nums + [1] dp = {}
def dfs(l, r): if l > r: return 0 if (l, r) in dp: return dp[(l, r)]
dp[(l, r)] = 0 for i in range(l, r + 1): coins = nums[l - 1] * nums[i] * nums[r + 1] coins += dfs(l, i - 1) + dfs(i + 1, r) dp[(l, r)] = max(dp[(l, r)], coins) return dp[(l, r)]
return dfs(1, len(nums) - 2)
Time complexity: O(n ^ 3)
Space complexity: O(n ^ 2)
Dynamic Programming (Bottom-Up)
def max_coins_bottom_up(nums: List[int]) -> int: n = len(nums) new_nums = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)] for l in range(n, 0, -1): for r in range(l, n + 1): for i in range(l, r + 1): coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1] coins += dp[l][i - 1] + dp[i + 1][r] dp[l][r] = max(dp[l][r], coins)
return dp[1][n]
Time complexity: O(n^3)
Space complexity: O(n^2)