Best Time to Buy and Sell Stock with Cooldown

At each day we track two states: buying (don't hold stock) and selling (hold stock). After selling, we skip one day (cooldown). Select an approach to visualize:

At each day i we have a state: buying (allowed to buy) or selling (holding stock). We explore both the action (buy/sell) and doing nothing (cooldown).

1. 1Base case: if i ≥ len(prices), return 0.
2. 2Buying state: either buy today (dfs(i+1, selling) − price) or skip.
3. 3Selling state: either sell today (dfs(i+2, buying) + price, skipping cooldown day) or skip.
4. 4Return the max of both options. Many states are recomputed — fixed by memoization.

def maxProfit(prices):
    def dfs(i, buying):
        if i >= len(prices): return 0
        cooldown = dfs(i + 1, buying)
        if buying:
            buy = dfs(i+1, not buying) - prices[i]
            return max(buy, cooldown)
        else:
            sell = dfs(i+2, not buying) + prices[i]
            return max(sell, cooldown)
    return dfs(0, True)

The recursion recomputes the same (i, buying) states repeatedly. There are only 2n unique states. Memoize each result — any repeated call is an O(1) cache lookup.

1. 1Add dp = {} before the recursive function.
2. 2At the start of each call, check if (i, buying) is in the cache. If so, return immediately.
3. 3Store the result before returning. The total number of unique computations drops from O(2ⁿ) to O(n).

def maxProfit(prices):
    dp = {}
    def dfs(i, buying):
        if i >= len(prices): return 0
        if (i, buying) in dp: return dp[(i, buying)]
        cooldown = dfs(i+1, buying)
        if buying:
            dp[(i,buying)] = max(dfs(i+1,not buying)-prices[i], cooldown)
        else:
            dp[(i,buying)] = max(dfs(i+2,not buying)+prices[i], cooldown)
        return dp[(i, buying)]
    return dfs(0, True)

Build the solution from the last day backward. dp[i][1] = max profit from day i when we can buy. dp[i][0] = max profit from day i when we hold stock.

1. 1Initialize dp[n][0] = dp[n][1] = 0 (no profit beyond last day).
2. 2For buying state: dp[i][1] = max(dp[i+1][0] − price, dp[i+1][1]).
3. 3For selling state: dp[i][0] = max(dp[i+2][1] + price, dp[i+1][0]) — selling jumps 2 days (cooldown).
4. 4Answer is dp[0][1].

def maxProfit(prices):
    n = len(prices)
    dp = [[0] * 2 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        buy = dp[i+1][0] - prices[i]
        dp[i][1] = max(buy, dp[i+1][1])
        sell = (dp[i+2][1] if i+2 <= n else 0) + prices[i]
        dp[i][0] = max(sell, dp[i+1][0])
    return dp[0][1]

The bottom-up solution only ever reads from dp[i+1] and dp[i+2]. Replace the table with three variables that shift forward each iteration.

1. 1dp1_buy: max profit at next day, buying state.
2. 2dp1_sell: max profit at next day, selling state.
3. 3dp2_buy: max profit two days ahead, buying state (for post-cooldown sell).
4. 4After computing current day, shift: dp2_buy ← dp1_buy, then update both dp1 values.

def maxProfit(prices):
    n = len(prices)
    dp1_buy, dp1_sell = 0, 0
    dp2_buy = 0
    for i in range(n - 1, -1, -1):
        dp_buy = max(dp1_sell - prices[i], dp1_buy)
        dp_sell = max(dp2_buy + prices[i], dp1_sell)
        dp2_buy = dp1_buy
        dp1_buy, dp1_sell = dp_buy, dp_sell
    return dp1_buy