burst_balloons.py

'''
https://leetcode.com/problems/burst-balloons/description/
'''
class Solution:
    def maxCoins(self, nums):
        nums = [1, *nums, 1]
        return self.dp(0, len(nums) - 1, nums, {})
    
    def dp(self, a, b, nums, memo):
        if abs(a - b) < 2: return 0
        if (a, b) in memo: return memo[(a, b)]
        sub_sol, side_prod = 0, nums[a] * nums[b]
        for i in range(a + 1, b):
            sub_sol = max(sub_sol, nums[i] * side_prod + self.dp(a, i, nums, memo) + self.dp(i, b, nums, memo))
        memo[(a, b)] = sub_sol
        return sub_sol