Burst Balloons

Intuition

Solution

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        for l in range(3, n+1):
            for left in range(0, n - l + 1):
                right = left + l - 1

                # for i in range(left + 1, right):
                #     dp[left][right] = max(
                #         dp[left][right],
                #         nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]
                #     )
                dp[left][right] = max([
                    nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right] for i in range(left+1, right)
                ])
        return dp[0][n-1]