class Solution:
def maxCoins(self, nums: List[int]) -> int:
news = [1] + nums + [1]
dp = [[0] * len(news) for _ in range(len(news))]
## dp[i][j] 是【0，n】 的乘值
for i in range(len(nums),-1,-1):
for j in range(i,len(nums)+2):
for k in range(i+1,j):
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + news[i]*news[j]*news[k])
return dp[0][-1]