[Leetcode 312] Burst Ballons

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

1) 코드

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        
        nums.insert(0, 1)
        nums.append(1)

        def recursive(i, j, memo):
            if i == j:
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            
            max_cost = float('-inf')

            for k in range(i, j):
                curr_cost = nums[i-1]*nums[k]*nums[j]
                left_cost = recursive(i, k, memo)
                right_cost = recursive(k+1, j, memo)

                max_cost = max(max_cost, curr_cost+left_cost+right_cost)
            
            memo[(i, j)] = max_cost

            return max_cost 

        memo = {}

        return recursive(1, len(nums)-1, memo)

2) 해설

• 재귀와 DP를 결합해서 푸는 문제이다.
• 특정 터트릴 위치를 골랐다면, 해당 위치의 각각 왼쪽과 오른쪽에 대해서
  재귀적으로 진입을 해서 값을 계산한다
• 결과적으로 각 재귀 단계에서 max_cost를 리턴해서 윗 단계로 보내준다
• 그리고 이 경우 반복되는 계산에 대해서는 시간 복잡도를 줄이기 위해서
  memoization을 사용한다.