<p>You are given <code>n</code> balloons, indexed from <code>0</code> to <code>n - 1</code>. Each balloon is painted with a number on it represented by an array <code>nums</code>. You are asked to burst all the balloons.</p>

<p>If you burst the <code>i<sup>th</sup></code> balloon, you will get <code>nums[i - 1] * nums[i] * nums[i + 1]</code> coins. If <code>i - 1</code> or <code>i + 1</code> goes out of bounds of the array, then treat it as if there is a balloon with a <code>1</code> painted on it.</p>

<p>Return <em>the maximum coins you can collect by bursting the balloons wisely</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,5,8]
<strong>Output:</strong> 167
<strong>Explanation:</strong>
nums = [3,1,5,8] --&gt; [3,5,8] --&gt; [3,8] --&gt; [8] --&gt; []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 100</code></li>
</ul>

class Solution:
    def maxCoins(self, nums: List[int]) -> int:        
        # def popIndex(nums, i):
        #     if len(nums) > 2:
        #         if i == 0:
        #             val = nums[0]*nums[1]
        #             del nums[0]
        #             return val
        #         elif i == len(nums)-1:
        #             val = nums[-1]*nums[-2]
        #             del nums[-1]
        #             return val
        #         else:
        #             val = nums[i-1]*nums[i]*nums[i+1]
        #             del nums[i]
        #             return val
        #     elif len(nums) == 2:
        #         val = nums[0]*nums[1]
        #         del nums[i]
        #         return val
        #     elif len(nums) == 1:
        #         val = nums[0]
        #         del nums[0]
        #         return val
        #     else:
        #         print("Strange error")

        #If there are 0s anywhere, remove them as they add nothing to the number of coins and should always be popped first
        i = 0
        while i < len(nums):
            if nums[i] == 0:
                del nums[i]
            else:
                i += 1

        def calcProd(nums, i, j):

            if i-1 >= 0:
                edge1 = nums[i-1]
            else:
                edge1 = 1

            if j+1 <= len(nums)-1:
                edge2 = nums[j+1]
            else:
                edge2 = 1

            prod = edge1*edge2 

            return prod 

        saved = {}
        def dpPop(nums, i, j):
            if (i,j) in saved:
                return saved[(i,j)]
            elif i > j:
                return 0
            elif i == j:
                prod = calcProd(nums, i, j)
                return prod*nums[i]

            prod = calcProd(nums, i, j)

            options = []

            for k in range(i, j+1):
                val = prod*nums[k]
                options.append(val + dpPop(nums, i, k-1)+ dpPop(nums, k+1, j))

            saved[(i,j)] = max(options)

            return max(options)
        
        out = dpPop(nums, 0, len(nums)-1)
        # print(saved)
        return out

        # save = {}

        # def recPop(nums):
        #     if len(nums) == 0:
        #         return 0

        #     elif len(nums) > 2:
        #         if tuple(nums) in save:
        #             return save[tuple(nums)]

        #         options = []
        #         for i in range(1, len(nums)-1):
        #             cop = nums.copy()
        #             val = popIndex(cop, i)
        #             val += recPop(cop)
        #             options.append(val)

        #         save[tuple(nums)] = max(options)
        #         return max(options)
        #     elif len(nums) == 1:
        #         return nums[0]
        #     elif len(nums) == 2:
        #         return nums[0]*nums[1] + max(nums)

        # return recPop(nums)

        # coins = 0
        # while len(nums) > 2:
        #     min_val, min_ind = 101, 0
        #     for i in range(1, len(nums)-1):
        #         if nums[i] < min_val:
        #             min_val = nums[i]
        #             min_ind = i

        #     coins += popIndex(nums, min_ind)

        # #At this point, nums has length of at most 2
        # if len(nums) == 2:
        #     coins += nums[0]*nums[1]
        #     if nums[1] < nums[0]:
        #         del nums[1]
        #     else:
        #         del nums[0]

        # if len(nums) == 1:
        #     coins += nums[0]

        # return coins
30134