On any given day you are in exactly one of three states: holding a share, just sold a share today (so tomorrow is a forced cooldown), or resting (not holding, free to buy). Each day’s best profit for a state only depends on yesterday’s states, which is what makes this a DP problem even though there is no explicit 2-D grid in the final solution — the “two dimensions” are day and state.
Brute Force Recursion
Time O(2^n)Space O(n)At every day, if you are not holding a stock you can either buy or do nothing; if you are holding, you can either sell (which forces a cooldown the next day) or do nothing. Try every branch and take the best.
class Solution: def maxProfit(self, prices: list[int]) -> int: n = len(prices) def rec(i: int, holding: bool) -> int: if i >= n: return 0 skip = rec(i + 1, holding) if holding: sell = prices[i] + rec(i + 2, False) return max(skip, sell) buy = -prices[i] + rec(i + 1, True) return max(skip, buy) return rec(0, False)Two choices per day, and the same (day, holding) pair recurs constantly across different decision paths — exponential blow-up.
State Machine DP (Bottom-Up)
OptimalTime O(n)Space O(1)Track the best possible profit for each of the three states after processing day i:
hold: currently holding a share.sold: sold a share today (tomorrow must be a cooldown).rest: not holding, and free to buy today.
Transitions, using yesterday’s values:
hold = max(hold, rest - prices[i])— keep holding, or buy today from a resting state.sold = hold + prices[i]— sell the share you were holding.rest = max(rest, sold)— keep resting, or a cooldown day has passed since the last sale.
class Solution: def maxProfit(self, prices: list[int]) -> int: if not prices: return 0 hold, sold, rest = -prices[0], 0, 0 for price in prices[1:]: prev_hold, prev_sold, prev_rest = hold, sold, rest hold = max(prev_hold, prev_rest - price) sold = prev_hold + price rest = max(prev_rest, prev_sold) return max(sold, rest)Watch the three state values update in place on prices = [1, 2, 3, 0, 2]: sold is never spendable the very next day — it only reaches hold through rest, which is exactly the forced cooldown.
Prices
Seed day 0 by buying: hold = -price = -1. sold and rest start at 0 because no share has been sold or rested yet.
Complexity: one pass over n days with O(1) work per day → O(n) time. Only three running values are kept → O(1) space.