Description
Maximize coins by bursting balloons.
Constraints
- Time Complexity:
O(n³) - Space Complexity:
O(n²)
Tags
arraydynamic-programming
def maxCoins(nums):
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)