[Problem] Best Time to Buy and Sell Stock with Cooldown

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples

Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:
Input: prices = [1]
Output: 0

Approach

The cooldown rule means your decision today depends on what you did yesterday.
Therefore, we use Dynamic Programming and track your state at the end of each day.

State Definitions

For each day i, we track three possible states:

1. rest[i]
   You do NOT hold a stock
   You are allowed to buy tomorrow

2. hold[i]
   You are currently holding one stock

3. cool[i]
   You SOLD today
   Tomorrow is a cooldown day (cannot buy)

These three states fully describe every valid situation.

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2: return 0
        
        # dp[i][0]=rest(can buy), dp[i][1]=hold, dp[i][2]=cooldown
        dp = [[0] * 3 for _ in range(n + 1)]
        
        for i in range(n-1, -1, -1):
            dp[i][0] = max(dp[i+1][0], -prices[i] + dp[i+1][1])
            dp[i][1] = max(dp[i+1][1], prices[i] + dp[i+1][2])
            dp[i][2] = dp[i+1][0]
            
        return dp[0][0]