312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

solution

# 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]

时间复杂度：O() 空间复杂度：O()