<jupyter_start><jupyter_text>说明：    给定n个气球，索引从0到n-1。    每个气球上都绘有一个数字，由数组nums表示。    你被要求炸开所有的气球。    如果你的气球爆了，你会得到 num[left]*nums[i]*nums[right]硬币。    这里的左和右是i的相邻索引。    在突发之后，左和右就成为相邻的。明智地炸开气球，找到你能收集到的最多的硬币。Note:1、You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.2、0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100Example:    Input: [3,1,5,8]    Output: 167     Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []                 coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167<jupyter_code>class Solution:
    def maxCoins(self, nums) -> int:
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        nums = [0] + nums
        len_n = len(nums)
        dp = [[0] * len_n for _ in range(len_n)] 
        
        for i in range(2, len_n+1):
            start = 1
            while start + i - 1 < len_n:
                end = start + i - 1
                dp[start][end] = max(dp[start][end], dp[start][end-1] + nums[start-1] * nums[i] * nums[end+1] + dp[start+1][end])
                start += 1
        print(dp)
        return dp[1][-1]
class Solution:
    def maxCoins(self, nums) -> int:
        if not nums: return 0
        nums_len = len(nums)
        nums = [1] + nums + [1]
        dp = [[0] * (nums_len + 2) for _ in range(nums_len + 2)] # 表示从 i -> j 射破气球所能获得的最高分数
        # nums区间的长度
        for gap in  range(1, nums_len+1):
            start = 1
            while start <= nums_len - gap + 1:
                end = start + gap - 1
                for k in range(start, end+1):
                    dp[start][end] = max(dp[start][end], dp[start][k-1] + dp[k+1][end] + nums[start-1] * nums[k] * nums[end+1])
                start += 1
        return dp[1][nums_len]
solution = Solution()
solution.maxCoins([3,1,5,8])<jupyter_output>[[0, 0, 0, 0, 0, 0], [0, 3, 30, 159, 167, 0], [0, 0, 15, 135, 159, 0], [0, 0, 0, 40, 48, 0], [0, 0, 0, 0, 40, 0], [0, 0, 0, 0, 0, 0]]
{'fraction_non_alphanumeric': 0.17349027635619244, 'fraction_numerical': 0.06857727737973388, 'mean_word_length': 1.9666160849772383, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '97134', 'license': 'Apache-2.0', 'n_tokens_mistral': 958, 'n_tokens_neox': 904, 'n_words': 202, 'path': 'Dynamic Programming/1005/312. Burst Balloons.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '1954'}