# https://leetcode.com/problems/burst-balloons/solutions/1659427/python-beginner-brute-force-recursion-brute-better-memoization-dp/
# https://www.cnblogs.com/niuyourou/p/11964842.html
# dp[i][j] = max([dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j])_{i <= k <= j}
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
dp = [[0] * len(nums) for _ in range(len(nums))]
for gap in range(len(nums)): # 从短的开始构建, 依次求打破一个气球的，打破两个气球的
for left in range(len(nums) - gap):
right = left + gap
res = 0
for k in range(left + 1, right):
res = max(res, dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right])
dp[left][right] = res
return dp[0][len(nums) - 1]