Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
312. Burst Balloons
class Solution:
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
return self.sol_dp(nums)
return self.rec(nums)
def sol_dp(self, nums):
nums = [1] + nums + [1]
mem = [[-1 for _ in nums] for _ in nums]
for i in range(1, len(nums)):
mem[i-1][i] = 0
for k in range(2, len(nums)):
for l in range(0, len(nums)-k):
r = l + k
for i in range(l+1, r):
mem[l][r] = max(mem[l][r], mem[l][i] + mem[i][r] + nums[l]*nums[i]*nums[r])
return mem[0][len(nums)-1]
def rec(self, nums):
nums = [1] + nums + [1]
mem = [[-1 for _ in nums] for _ in nums]
def mc(l, r):
if mem[l][r] != -1:
return mem[l][r]
ans = 0
for i in range(l+1, r):
ans = max(ans, mc(l, i) + mc(i, r) + nums[l]*nums[i]*nums[r])
mem[l][r] = ans
return ans
ans = mc(0, len(nums)-1)
return ans
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.