题目描述

按照雪菜大佬的解法写的，翻译成python

解法

class Solution(object):
    def maxCoins(self, nums):

    nums = [1] + nums + [1]
    # dp[i,j]表示集合中[i+1,j-1]气球打完的最大值方案
    dp = [[0] * len(nums) for i in range(len(nums))]

    # 因为我们一个区间，有三个指针，所以初始长度最少为3
    # 我们这个区间的最大范围是len(num)
    for midRange in range(3, len(nums) + 1):
        # i是中间区间的左边界
        i = 0
        while i + midRange - 1 < len(nums):
            # j最多到len(nums) - 1
            j = i + midRange - 1

            # k的移动范围[i+1, j-1]
            # 这个区间内i*k*j的最大值 max(nums[i]*nums[k]*nums[j])
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j])
            i += 1

    return dp[0][-1]