python - 爆破气球在leetcode中超时

给定n个气球，索引范围从0到n-1每个气球上都绘有一个由数组nums表示的数字你被要求炸掉所有的气球。如果你的气球爆了，我会给你金币。这里，左和右是i的相邻索引。在突发之后，左和右就变成相邻的。
找出最大的硬币，你可以收集气球爆裂明智。
nums=[3,1,5,8]-->[3,5,8]-->[3,8]-->[8]-->[]
硬币=3*1*5+3*5*8+1*3*8+1*8*1=167
我有时间去做一些测试用例。
想知道如何改进请只给我提示。

class Solution(object):
        def recursion(self, nums, index, dp):
            r = -1
            if not nums:
                return 0
            if len(nums) == 1:
                return nums[0]
            if str(nums) in dp:
                return dp[str(nums)]
            if index >= len(nums):
                return 0
            for i in range(len(nums)):
                if i == 0:
                    r = max(r, nums[i]*nums[i+1] + self.recursion(nums[0:i]+nums[i+1:][:], i, dp))
                elif i == len(nums)-1:
                    r = max(r, nums[i-1]*nums[i] + self.recursion(nums[0:i]+nums[i+1:][:], i, dp))
                else:
                    r = max(r, nums[i-1]*nums[i]*nums[i+1] + self.recursion(nums[0:i]+nums[i+1:][:], i, dp))
            dp[str(nums)] = r
            return r

        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return self.recursion(nums, 0, {})

最佳答案

提示：尽量避免在每次递归中复制列表。
P.S.：我敢肯定，有一个动态编程解决方案，时间复杂度为O（n ^ 3）。

关于python - 爆破气球在leetcode中超时，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46069244/