破裂的氣球在代碼中超時

Question

給定n個氣球，索引從0到n-1。每個氣球上都繪有一個由數組numn表示的數字。你被要求爆破所有的氣球。如果你爆破氣球我你會得到數[左] *數[我] *數[右]硬幣。這裏左邊和右邊是i的相鄰指數。爆炸之後，左邊和右邊然後變得相鄰。

找到你可以通過明智地爆破氣球收集的最大金幣。

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）。