burst_balloons
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def maxCoins(self, nums: list[int]) -> int: 7 """ 8 We want to be able to get the maximum coins by bursting balloons. 9 This is a 2D DP problem. 10 11 First, we can handle edge cases by adding the 1s to the end of our 12 current nums. 13 14 Next, we define the dp function, which returns the max gain for popping 15 this particular window of balloons. 16 17 The dp function iterates through all the balloons and keeps track of 18 popping the ith balloon last. 19 20 We then keep the max of this by the end. 21 22 Finally, we call the dp function, but give the range removing the balloons 23 we added in. 24 """ 25 nums = [1] + nums + [1] 26 27 @cache 28 def dp(l, r): 29 if l > r: 30 return 0 31 result = 0 32 33 for i in range(l, r + 1): 34 gain = nums[l - 1] * nums[i] * nums[r + 1] 35 remaining = dp(l, i - 1) + dp(i + 1, r) 36 result = max(result, remaining + gain) 37 38 return result 39 40 return dp(1, len(nums) - 2) 41 42 43# @leet end 44 45 46def test(): 47 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def maxCoins(self, nums: list[int]) -> int: 8 """ 9 We want to be able to get the maximum coins by bursting balloons. 10 This is a 2D DP problem. 11 12 First, we can handle edge cases by adding the 1s to the end of our 13 current nums. 14 15 Next, we define the dp function, which returns the max gain for popping 16 this particular window of balloons. 17 18 The dp function iterates through all the balloons and keeps track of 19 popping the ith balloon last. 20 21 We then keep the max of this by the end. 22 23 Finally, we call the dp function, but give the range removing the balloons 24 we added in. 25 """ 26 nums = [1] + nums + [1] 27 28 @cache 29 def dp(l, r): 30 if l > r: 31 return 0 32 result = 0 33 34 for i in range(l, r + 1): 35 gain = nums[l - 1] * nums[i] * nums[r + 1] 36 remaining = dp(l, i - 1) + dp(i + 1, r) 37 result = max(result, remaining + gain) 38 39 return result 40 41 return dp(1, len(nums) - 2)
def
maxCoins(self, nums: list[int]) -> int:
7 def maxCoins(self, nums: list[int]) -> int: 8 """ 9 We want to be able to get the maximum coins by bursting balloons. 10 This is a 2D DP problem. 11 12 First, we can handle edge cases by adding the 1s to the end of our 13 current nums. 14 15 Next, we define the dp function, which returns the max gain for popping 16 this particular window of balloons. 17 18 The dp function iterates through all the balloons and keeps track of 19 popping the ith balloon last. 20 21 We then keep the max of this by the end. 22 23 Finally, we call the dp function, but give the range removing the balloons 24 we added in. 25 """ 26 nums = [1] + nums + [1] 27 28 @cache 29 def dp(l, r): 30 if l > r: 31 return 0 32 result = 0 33 34 for i in range(l, r + 1): 35 gain = nums[l - 1] * nums[i] * nums[r + 1] 36 remaining = dp(l, i - 1) + dp(i + 1, r) 37 result = max(result, remaining + gain) 38 39 return result 40 41 return dp(1, len(nums) - 2)
We want to be able to get the maximum coins by bursting balloons. This is a 2D DP problem.
First, we can handle edge cases by adding the 1s to the end of our current nums.
Next, we define the dp function, which returns the max gain for popping this particular window of balloons.
The dp function iterates through all the balloons and keeps track of popping the ith balloon last.
We then keep the max of this by the end.
Finally, we call the dp function, but give the range removing the balloons we added in.
def
test():