leetcode 爆破气球超时

Question

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

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

我要抽出一些时间来做一些测试用例。

想知道如何改进？请只给我提示。

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, {})

Answer 1

提示：尽量避免在每次递归中复制列表。

p.s.: 我很确定有一个时间复杂度为 O(n^3) 的动态规划解决方案。

leetcode 爆破气球超时

Bursting baloon is timing out in leetcode

python

algorithm

recursion

memoization