312戳气球

    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 状态res[left][right]代表把left到right之间的气球戳破(不包括left和right)能获得的最大收益
        # 转移方程: res[left][right] = max(res[left][k] + res[k][right] + nums[left] * nums[k] * nums[right])
        # k从left+1到right(不包括right)
        # 这题的特点是转移方程不是一个简单的公式,而是for循环求max获得的
        
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        n = len(nums) + 2

        res = []
        for i in range(n):
            temp = [0] * n
            res.append(temp)

        temp = nums
        nums = [1]
        nums.extend(temp)
        nums.append(1)

        for delta in range(2, n):
            for left in range(n - delta):
                right = left + delta
                tmp = []
                for k in range(left + 1, right):
                    tmp.append(res[left][k] + res[k][right] + nums[left] * nums[k] * nums[right])
                res[left][right] = max(tmp)
        return res[0][n - 1]