DP on Stocks

Six LeetCode problems — 121, 122, 123, 188, 309 and 714 — look like six problems and are one. Each is a small variation on a single state machine, and once you can draw that machine the recurrence writes itself. People who memorise them individually get six chances to forget; people who learn the machine get one thing to remember and can derive any variant, including ones they have not seen.

What you’ll learn

• The two-state machine behind all unlimited-transaction stock problems.
• How a cooldown, a fee, or a transaction limit each add exactly one thing to the machine — and nothing else changes.
• Why the answer is never the hold state.
• The $O(1)$-space form, and how to derive it from the table form.

The cue

You are looking at stock DP when…

• The input is a list of prices over time and you choose when to buy and sell.
• There is a constraint on how you may trade: at most one transaction, unlimited transactions, at most k, a one-day cooldown after selling, or a fee per trade.
• You must hold at most one share at a time — that is what makes the state space tiny and the problem tractable.

The reframe that unlocks all of them: stop thinking about which days to buy and sell. Think about what state you are in each day — holding a share, or not — and what it costs to move between states. The days become transitions.

Reach for something else when you may hold multiple shares (that is a different, usually greedy, problem), or when the question is the maximum subarray rather than a buy/sell pair — that is Kadane’s.

Visual intuition

Two states, four transitions. Every day you pick an edge:

stateUnlimited transactions: hold, or do not holdLC 122 · O(n) time, O(1) space

1def max_profit(prices):2    hold, free = -prices[0], 03    for p in prices[1:]:4        hold = max(hold, free - p)   # keep, or buy today5        free = max(free, hold + p)   # stay out, or sell today6    return free

hold-7free0

day 0Two states only, because with unlimited transactions and no cooldown you are either holding a share or you are not. Every day you choose an edge.

Play‹›1/7⟲

The numbers under each state are the best profit achievable while in that state. Every day both states update from the previous day's values, and the answer is the 'free' state — never 'hold', because ending while still owning a share means the money was never realised.

Now add a cooldown. One extra state, and the recurrence changes in exactly one place:

stateAdd a cooldown and you add a state, not a rewriteLC 309

1def max_profit(prices):2    hold = -prices[0]      # own a share3    sold = 0               # just sold — must cool down4    rest = 0               # free to buy5    for p in prices[1:]:6        prev_sold = sold7        sold = hold + p            # sell today8        hold = max(hold, rest - p) # keep holding, or buy today9        rest = max(rest, prev_sold)  # stay free, or finish cooling down10    return max(sold, rest)

hold-1sold0rest0

day 0Three states, and the transitions between them *are* the recurrence. On day 0 the only meaningful choice is to buy or not: holding costs 1, so hold = −1. Being in "sold" or "rest" with no trades yet is worth 0.

Play‹›1/10⟲

The 'rest' state reads YESTERDAY's 'sold' value, not today's. That one-day lag IS the cooldown, and it is why a prev_sold temporary is needed. Overwrite sold before rest reads it and the cooldown silently vanishes while the code still looks correct.

The template

stock_state_machine.py

def max_profit_unlimited(prices):           # LC 122
    hold, free = -prices[0], 0
    for p in prices[1:]:
        hold = max(hold, free - p)           # keep holding, or buy today
        free = max(free, hold + p)           # stay out, or sell today
    return free                              # never `hold`
 
 
def max_profit_with_fee(prices, fee):        # LC 714
    hold, free = -prices[0], 0
    for p in prices[1:]:
        hold = max(hold, free - p)
        free = max(free, hold + p - fee)     # the ONLY change: pay on sale
    return free
 
 
def max_profit_cooldown(prices):             # LC 309
    hold, sold, rest = -prices[0], 0, 0
    for p in prices[1:]:
        prev_sold = sold                     # the cooldown lives in this line
        sold = hold + p
        hold = max(hold, rest - p)
        rest = max(rest, prev_sold)
    return max(sold, rest)
 
 
def max_profit_k(prices, k):                 # LC 123 (k=2) and LC 188
    if k >= len(prices) // 2:                # k so large it is unlimited
        return max_profit_unlimited(prices)
    hold = [float("-inf")] * (k + 1)
    free = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            hold[t] = max(hold[t], free[t - 1] - p)   # buying starts transaction t
            free[t] = max(free[t], hold[t] + p)
    return free[k]
 
 
print(max_profit_unlimited([7, 1, 5, 3, 6, 4]))   # expect 7
print(max_profit_with_fee([1, 3, 2, 8, 4, 9], 2)) # expect 8
print(max_profit_cooldown([1, 2, 3, 0, 2]))       # expect 3
print(max_profit_k([3, 2, 6, 5, 0, 3], 2))        # expect 7

Dry run

LC 122, prices = [7, 1, 5, 3, 6, 4]. Read the two columns as “best profit if I end today in this state”.

day	price	hold	free	reasoning
0	7	−7	0	buying costs 7; not buying is worth 0
1	1	−1	0	better to be holding a share bought at 1 than at 7
2	5	−1	4	sell the share bought at 1
3	3	1	4	buy again from a base of 4: 4 − 3 = 1
4	6	1	7	sell: 1 + 6 = 7
5	4	3	7	selling at 4 gives 5, worse than 7

Answer 7, from buying at 1, selling at 5, buying at 3, selling at 6.

Two things worth stating out loud:

• hold is negative early on and that is correct. It is profit-so-far, and owning a share you paid for is a debt until you sell. Initialising it to 0 instead of -prices[0] is the standard bug and produces answers that are too large.
• free reads the just-updated hold. That permits buying and selling on the same day, which is a no-op worth 0 and therefore harmless — and it is exactly what unlimited transactions allow. In the cooldown version the same shortcut would destroy the constraint, which is why that one needs the temporary.

Complexity

Problem	Time	Space
LC 121 (one transaction)	$O(n)$	$O(1)$
LC 122 (unlimited)	$O(n)$	$O(1)$
LC 714 (fee)	$O(n)$	$O(1)$
LC 309 (cooldown)	$O(n)$	$O(1)$
LC 123 (k = 2)	$O(n)$	$O(1)$ — four named variables
LC 188 (arbitrary k)	$O(n \cdot k)$	$O(k)$

The k >= n // 2 shortcut in LC 188 matters: without it, a large k makes the $O(n \cdot k)$ loop time out even though the answer is just the unlimited case. Any k above n // 2 cannot constrain you, because there are not enough days to use that many transactions.

The variant map

Problem	Constraint	What changes
121	at most one transaction	hold = max(hold, -p) — buying always starts from 0, never from accumulated profit
122	unlimited	the base machine
714	fee per transaction	subtract fee on the sell edge
309	one-day cooldown	add a rest state; rest reads yesterday’s sold
123	at most 2 transactions	two (hold, free) pairs, chained
188	at most k transactions	arrays of length k + 1, plus the k >= n // 2 shortcut

LC 121 is the one that is not really DP

With a single transaction the machine collapses: track the minimum price seen so far and the best profit against it, in one pass. Recognising that the general machine also solves it — with hold = max(hold, -p) instead of max(hold, free - p) — is the useful insight, because it shows the difference is one term.

Pitfalls

• Initialising hold to 0. It must be -prices[0], or -inf if you loop from day 0. Zero implies you acquired a share for free.
• Returning hold. Ending while holding means the profit was never realised. Return free (or max(sold, rest) with a cooldown).
• Overwriting sold before rest reads it in LC 309. That deletes the cooldown, and the code still looks right.
• Forgetting the k >= n // 2 shortcut in LC 188. With k = 10^9 the straightforward loop times out on a problem whose answer is trivial.
• Applying the fee on both edges. Charge it once per completed transaction — conventionally on the sell.
• Using LC 122’s greedy one-liner everywhere. “Sum every positive consecutive difference” is correct only for unlimited transactions with no fee and no cooldown. Add any constraint and it silently breaks.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is the answer never hold?”	Whether you understand the states	Being in hold means still owning a share, so the profit is unrealised. Only a state with no position represents money you actually have
“LC 122 has a greedy one-liner. Why bother with DP?”	Judgement	The greedy sums positive consecutive differences and is correct only with no fee and no cooldown. The machine survives every variant; the greedy survives none
“Now k can be $10^9$”	Whether you spot the degenerate case	If k >= n // 2 there are not enough days to constrain you, so it reduces to unlimited. Without that check the $O(nk)$ loop times out
“Add a two-day cooldown”	Whether you can extend the machine	Add another rest state, or index the rest by days-since-sale. The structure is unchanged, which is the point of the framing
“Reduce the space in LC 188”	Space reasoning	Each day reads only the previous day, so two rows of length k + 1 suffice — and with care, one row iterated in the right direction
“What if you can hold multiple shares?”	Whether you know the boundary	The state space is no longer two-valued and this framing breaks. That becomes a different, usually greedy, problem

Practice

4 problems

0 easy2 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○122Best Time to Buy and Sell Stock IImediumLeetCode Top Interview 150
• ○309Best Time to Buy and Sell Stock with CooldownmediumNeetCode 150
• ○123Best Time to Buy and Sell Stock IIIhardLeetCode Top Interview 150
• ○188Best Time to Buy and Sell Stock IVhardLeetCode Top Interview 150

Exercises

LC 122 — Best Time to Buy and Sell Stock II · Medium

pch.exerciseTag pch.exerciseTitle

LC 714 — With Transaction Fee · Medium

pch.exerciseTag pch.exerciseTitle

LC 309 — With Cooldown · Medium

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag DP on stocks — self-check

1. Why must `hold` be initialised to -prices[0] rather than 0?

   A To avoid a division by zero B Because hold is profit-so-far, and owning a share you paid for is a debt until you sell — zero would imply acquiring it free C Because prices can be negative D It makes no difference
   pch.quizShowAnswer

   B — Because hold is profit-so-far, and owning a share you paid for is a debt until you sell — zero would imply acquiring it free — Initialising to 0 produces answers that are too large, because it treats the first purchase as costless. Either -prices[0] with the loop starting at day 1, or -inf with the loop starting at day 0.

2. Why is the answer never the `hold` state?

   A Because hold is always negative B Because being in hold means still owning a share, so the profit is unrealised — only a no-position state represents money you actually have C Because the problem forbids it D It can be, on some inputs
   pch.quizShowAnswer

   B — Because being in hold means still owning a share, so the profit is unrealised — only a no-position state represents money you actually have — This is the cleanest one-sentence statement of what the states mean, and it generalises: with a cooldown the answer is max(sold, rest), because both are no-position states.

3. In LC 309 the cooldown, where exactly does the constraint live?

   A In the number of states B In `rest` reading YESTERDAY's `sold` — the one-day lag is the cooldown, which is why a prev_sold temporary is needed C In the return statement D In the initialisation
   pch.quizShowAnswer

   B — In `rest` reading YESTERDAY's `sold` — the one-day lag is the cooldown, which is why a prev_sold temporary is needed — Overwrite sold before rest reads it and the cooldown vanishes while the code still looks correct. The temporary is not stylistic; it is the constraint.

4. LC 188 allows arbitrary k, and k can be 10^9. What must you check first?

   A Whether prices is empty B Whether k >= n // 2 — if so there are not enough days to constrain you, so it reduces to the unlimited case C Whether k is even D Nothing — the loop handles it
   pch.quizShowAnswer

   B — Whether k >= n // 2 — if so there are not enough days to constrain you, so it reduces to the unlimited case — Without the shortcut the O(n·k) loop times out on a problem whose answer is trivially the unlimited case. Each transaction needs at least two days, hence n // 2.

5. LC 122 has a famous greedy one-liner. Why learn the state machine anyway?

   A The greedy is wrong B The greedy is correct only with unlimited transactions, no fee and no cooldown — the machine survives every variant, the greedy survives none C The machine is faster D Interviewers forbid the greedy
   pch.quizShowAnswer

   B — The greedy is correct only with unlimited transactions, no fee and no cooldown — the machine survives every variant, the greedy survives none — Summing positive consecutive differences works for exactly one of the six problems. Deriving the other five from the machine is far more reliable than memorising five special cases.

Recall card

• Cue — prices over time, plus a constraint on how you may trade, holding at most one share.
• The machine — states are hold (own a share) and free (own nothing). Each day, every state updates from yesterday’s states.
• Base recurrence — hold = max(hold, free - p); free = max(free, hold + p).
• Each constraint adds one thing — a fee subtracts on the sell edge; a cooldown adds a rest state reading yesterday’s sold; a limit k adds a dimension.
• Initialise hold = -prices[0], return free — never hold.
• LC 188 — check k >= n // 2 first and fall back to unlimited.

Recap

• Six LeetCode problems, one state machine. Draw the states and transitions and the recurrence is readable off the diagram.
• hold and free are “best profit while in this state”, which is why hold starts negative and why the answer is never hold.
• A fee, a cooldown, or a transaction cap each modify the machine in exactly one place. Nothing else changes.
• $O(n)$ time and $O(1)$ space for everything except arbitrary k, which is $O(n \cdot k)$ time and $O(k)$ space — with a shortcut for large k.

Next: Bitmask and Tree DP — what to do when the DP state is a set rather than an index, and why “n ≤ 20” in a problem statement is a hint.