[Leetcode 309] Best Time to Buy and Sell Stock with Cooldown

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

1) 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        dp = {}

        def dfs(i, buying):
            if i >= len(prices):
                return 0

            if (i, buying) in dp:
                return dp[(i, buying)]

            maxProfit = 0 

            if buying:
                sell = dfs(i+2, not buying) + prices[i]
                cooldown = dfs(i+1, buying) 
                maxProfit = max(sell, cooldown)
            else:
                buy = dfs(i+1, not buying) - prices[i]
                cooldown = dfs(i+1, buying)
                maxProfit = max(buy, cooldown)

            dp[(i, buying)] = maxProfit

            return maxProfit 

        return dfs(0, False)

2) 설명

• DP와 DFS를 결합해서 푸는 문제이다.
• 사용자의 상태는 2가지이다. 바로 buy한 상태, buy하지 않은 상태
  이 2가지를 dfs의 인자로 전달해서 구분해주면서,
  (1) buy한 상태에서는, sell, cooldown이라는 2가지 action이 가능
  (2) sell한 상태에서는, buy, cooldown이라는 2가지 action이 가능
  하도록 설계한다
• 그리고 sell을 했을 때는, 주식 가격만큼 수익을 추가하고,
  buy를 했을 때는, 주식 가격만큼 수익을 감소시킨다.
• 또한, DP의 memoization을 활용해서 i(인덱스)와 buying(상태값)
  을 저장함으로써, 중복된 값에 대한 계산을 막는다.