# Python Solution Using DP/Memorized-search

• Just paste my Accepted code here for reference, welcome comments and corrections :D

Memorized-search

``````def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums) == 0: return 0
self.memo = [[-1 for __ in xrange(len(nums)+2)] for _ in xrange(len(nums)+2)]
return self.burst([1,] + nums + [1, ], 0,  len(nums)+1)

def burst(self, balloons, left, right):
if left + 2 > right: return 0
if left + 2 == right:
return balloons[left] * balloons[left+1] * balloons[right]
if self.memo[left][right] != -1: return self.memo[left][right]
ans = 0
for i in xrange(left+1, right):
ans = max(ans, balloons[i] * balloons[left] * balloons[right] + self.burst(balloons, left, i) + self.burst(balloons, i, right))
self.memo[left][right] = ans
return ans
``````

DP

``````def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums) == 0: return 0
values = [1,] + nums + [1,]
dp = [[0 for _ in values] for __ in values]

for length in xrange(1, len(nums)+1):
for left in xrange(0, len(nums)+1-length):
right = left + length + 1
new = 0
for last in xrange(left+1, right):
new = max(new, values[last]*values[left]*values[right] + dp[left][last] + dp[last][right])
dp[left][right] = new
return dp[0][-1]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.