<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:
        size = len(nums)
        dp = [[0] * size for _ in range(size)]

        def cal_max_points(nums: List[int], left: int, right: int) -> int:
            if left > right:
                return 0

            if dp[left][right] != 0:
                return dp[left][right]
            
            for curr_i in range(left, right + 1):
                left_half = cal_max_points(nums, left, curr_i - 1)
                right_half = cal_max_points(nums, curr_i + 1, right)

                # only left, curr_i, and right has remained now.
                prev_num = 1 if left == 0 else nums[left - 1]
                next_num = 1 if right == size - 1 else nums[right + 1]
                dp[left][right] = max(dp[left][right], prev_num * nums[curr_i] * next_num + left_half + right_half)

            return dp[left][right]
        
        return cal_max_points(nums, left=0, right=size - 1)

        # Backtracking - slow
        # def get_points(index: int, nums: List[int], skip: set[int]) -> int:
        #     prev_index = index - 1
        #     while prev_index >= 0 and prev_index in skip:
        #         prev_index -= 1
        #     prev = nums[prev_index] if prev_index >= 0 else 1

        #     next_index = index + 1
        #     while next_index < len(nums) and next_index in skip:
        #         next_index += 1
        #     next = nums[next_index] if next_index < len(nums) else 1

        #     return prev * nums[index] * next

        # def get_max_points(nums: List[int], skip: set[int]):
        #     size = len(nums)
        #     if size == 1:
        #         return nums[0]

        #     max_val = 0
        #     for i in range(size):
        #         if i in skip:
        #             continue 
        #         skip.add(i)
        #         max_val = max(max_val, get_points(i, nums, skip) + get_max_points(nums, skip))
        #         skip.remove(i)
        #     return max_val

        # return get_max_points(nums, skip=set())
23003