#coding=utf-8
# 递归
class Solution1(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.res = 0
if not nums:
return self.res
self.res = self.getMaxValue(nums)
print self.res
return self.res
def getMaxValue(self,nums):
nLen = len(nums)
if nLen == 1:
return nums[0]
maxRes = 0
for i in range(nLen):
if i == 0 :
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes,nums[i]*nums[i+1]+self.getMaxValue(temp))
elif i == nLen-1:
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes, nums[i] * nums[i-1]+self.getMaxValue(temp))
else:
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes, nums[i-1]* nums[i]*nums[i+1]+ self.getMaxValue(temp))
return maxRes
# 记忆化递归
class Solution2(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.res = 0
if not nums:
return self.res
self.memo = {}
self.res = self.getMaxValue(nums)
print self.res
return self.res
def getMaxValue(self,nums):
nLen = len(nums)
if nLen == 1:
key = tuple(nums)
self.memo[key] = nums[0]
return nums[0]
key = tuple(nums)
if self.memo.has_key(key):
return self.memo[key]
maxRes = 0
for i in range(nLen):
if i == 0 :
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes,nums[i]*nums[i+1]+self.getMaxValue(temp))
elif i == nLen-1:
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes, nums[i] * nums[i-1]+self.getMaxValue(temp))
else:
temp = nums[0:]
temp.pop(i)
maxRes = max(maxRes, nums[i-1]* nums[i]*nums[i+1]+ self.getMaxValue(temp))
self.memo[key] = maxRes
return maxRes
#动态规划
# 见解题报告
class Solution3(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
s = Solution2()
n1 = [3,1,5,8]
n2 = [5,8]
n3 = [3,5,8]
n4 = [7,9,8,0,7,1,3,5,5,2,3]
n5 = [8,3,4,3,5,0,5,6,6,2,8,5,6,2,3,8,3,5,1,0,2]
s.maxCoins(n4)
