def maxCoins(self, nums: List[int]) -> int:

dp = [[-1 for i in range(len(nums))] for i in range(len(nums))]

if len(nums) == 1: return nums[0]

n = len(nums)

# calculate the case that i is the last burst ballon

def recur(start, end):

if start > end:

return 0

elif dp[start][end] != -1:

return dp[start][end]

elif start == end:

if start == 0:

dp[start][end] = nums[0] * nums[1]

return dp[start][end]

if end == n - 1:

dp[start][end] = nums[-1] * nums[-2]

return dp[start][end]

else:

dp[start][end] = nums[start - 1] * nums[start] * nums[start + 1]

return dp[start][end]

elif start < end:

for i in range(start, end + 1):

left = nums[start - 1] if start >= 1 else 1

right = nums[end + 1] if end < n - 1 else 1

dp[start][end] = max(dp[start][end], recur(start, i-1) + recur(i + 1, end) + nums[i] * left * right)

return dp[start][end]

def maxCoins(self, nums: List[int]) -> int:

# 为了方便记录首位的特殊情况，可以讲nums的首尾拼接两个[1]

nums = [1] + nums + [1]

# 为了避免多次求len(nums)，可以先将长度值存下来

n = len(nums)

# dp可以直接用0初始化

dp = [[0 for i in range(len(nums))] for i in range(len(nums))]

def recur(start, end):

# 数值0可以做bool变量使用，等于False

# 关于边界的选取有技巧这里，start和end表示数组的外包，这样避免出现了边界start > end的情况

if dp[start][end] or start + 1 == end:

return dp[start][end]

# 用coins作为临时变量存储

coins = 0

# 因为start end 为数组外包，因此可以只迭代内部元素

for k in range(start + 1, end):

coins = max(coins, recur(start, k) + recur(k, end) + nums[k] * nums[start] * nums[end])

dp[start][end] = coins

return coins