```
"""Every element in the given list has two roles:
1. as the element to disappear lastly
2. as the boundary for the subarray if it will disappear lastly
"""
def maxCoins(self, nums):#bottom up with rescursive
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in xrange(n)]#avoiding duplication
#define the boundary
def helper(left, right):
if right-left <=1:#if there are 1 or 2 elements
return 0
if dp[left][right]:
return dp[left][right]
res = []
for last in range(left+1, right):#choose which element to finish lastly and caculate sub array
res.append(nums[left]*nums[last]*nums[right]+helper(left, last)+helper(last,right))
dp[left][right] = max(res)
return dp[left][right]
return helper(0,len(nums)-1)
```