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

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

Each day has either 3 state :  Buy, Sell, CoolDown

On day i:

If it is in "buy" state, then it either buy stock on the last day, or it buy stock on day i ( cool down on last day ) .

If it is in "sell" state, then it either sell stock on the last day, or it sell stock on day i.

If it is in "cooldown" state, then it either cool down on last day, or it sell stock on last day.

Helper(i, state) returns the maximum profit on day i  in  x state.

To get the maximum profit on the last day,  it returns the profit can be made on the last day in "sell" state.

Top-Down Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, cooldown = 0, 1, 2
        
        @lru_cache(maxsize = None)
        def helper(i, state):
            if i < 0:
                return 0
            
            if i == 0 and state == sell:  
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == cooldown:
                return 0
            
            if state == buy:
                # max(buy-on-last-day,  buy-on-day-i)
                return max(helper(i-1, buy), -1 * prices[i] + helper(i-1, cooldown))
            
            if state == sell:
                # max(sell-on-last-day, sell-on-day-i)
                return max(helper(i-1, sell), prices[i] + helper(i-1, buy))
            
            if state == cooldown:
                # max(continue-cool-down, sell-on-last-day)
                return max(helper(i-1, cooldown), helper(i-1, sell)
    
        return helper(len(prices)-1, sell)

Bottom-Up Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if not prices:
            return 0
        
        buy = [0] * len(prices)
        sell = [0] * len(prices)
        cooldown = [0] * len(prices)
        
        buy[0] = -prices[0]
        
        for i in range(1, len(prices)):
            buy[i] = max(buy[i-1], -1 * prices[i] + cooldown[i-1])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
            cooldown[i] = max(cooldown[i-1], sell[i-1]) 
            
        return sell[-1]