[LeetCode] 312. Burst Ballons

 Problem : https://leetcode.com/problems/burst-balloons/

Time Complexity = O ( N ** 3 ) 

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        @lru_cache(maxsize = None)
        def dp(left, right):
            """
            maximumal coins can get for section section(left : right)
            left and right is excluded from this section
            """
            
            if left + 1 == right:
                # not include left and right
                return 0
            
            result = 0
            for i in range(left+1, right):
                # Balllon list = nums[left] , section(left, i), nums[i], section(i, right), nums[right]
                # tmpResult = nums[left] * nums[i] * nums[right] + max coins of section(left,i) + max coins of section(i, right)
                tmp = nums[left] * nums[i] * nums[right]
                tmp += dp(left, i)
                tmp += dp(i, right)
                result = max(result,  tmp)
            
            return result
        
        
        return dp(0, len(nums) - 1)