```
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1]+nums+[1]
dp = [[0] * len(nums) for i in ' ' * len(nums)]
for start in range(len(nums) - 2, 0, -1):
for end in range(start, len(nums) - 1):
for k in range(start, end+1): #nums[k] is the last balloon in nums[start...end]
dp[start][end] = max(dp[start][end], dp[start][k-1] + dp[k+1][end] + nums[start-1] * nums[k] * nums[end+1])
return dp[1][len(nums)-2]
```