The idea: one number per state, not one per day

In a one-row DP such as House Robber, each index gets one number. Some problems need more: what you may do tomorrow depends on where you are today. Then each day gets one cell per state, and the arrows between states say which cell of yesterday feeds which cell of today. The arrows form a small state machine.

Three states: REST (no share), HOLD (own one share) and SOLD (sold today). Arrows: rest to rest (wait), rest to hold (buy, minus p), hold to hold (keep), hold to sold (sell, plus p), sold to rest (cooldown). There is no arrow from sold to hold
With a cooldown, the only way back to buying runs through rest. Each arrow becomes one term of a max.

The problem and its three states

You are given the price of one stock for n days. You may buy and sell many times, but you hold at most one share, and after each sale there is a cooldown: you can't buy on the next day. At the end of day i you are in one of three states:

StateMeaning at the end of day iCan come from (day i−1)
holdyou own one sharehold (keep it), rest (buy today at p)
soldyou sold your share todayhold (sell today at p)
restno share, free to buy tomorrowrest (wait), sold (the cooldown day)

Each cell holds the best profit so far (cash in hand) for that state. Reading the arrows off the figure gives:

hold[i] = max( hold[i-1],  rest[i-1] - p[i] )      keep, or buy
sold[i] = hold[i-1] + p[i]                         sell
rest[i] = max( rest[i-1],  sold[i-1] )             wait, or cooldown
start:   hold[0] = sold[0] = -infinity,  rest[0] = 0
answer = max( sold[n], rest[n] )

The start column says that before day 1 you own nothing. hold[0] = −∞ means "impossible", so nothing can be sold on day 1. The answer never ends in hold: a share bought and not sold only costs money.

Worked example: 1 2 3 0 2

The table fills one column at a time, top to bottom (Demo: cooldown on 1 2 3 0 2). On day 3, sold[3] = hold[2] + 3 = −1 + 3 = 2: selling at 3 looks best. But day 4 is then a cooldown, and the cheap price 0 can't be used. The DP keeps both stories side by side: rest[3] = sold[2] = 1 remembers the earlier sale at 2, so hold[4] = rest[3] − 0 = 1, and sold[5] = 1 + 2 = 3.

Table for prices 1 2 3 0 2 with rows hold, sold, rest and days 0 to 5. hold: minus infinity, -1, -1, -1, 1, 1. sold: minus infinity, minus infinity, 1, 2, -1, 3. rest: 0, 0, 0, 1, 2, 2. The traced path: rest 0, buy day 1, sell day 2, cooldown day 3, buy day 4, sell day 5, profit 3
The traced path: buy 1, sell 2, cooldown, buy 0, sell 2. Profit 3, not the 2 you get by selling at the peak.

Which days? The trace back

The last column gives the profit, not the trades. Remember, for each cell, which arrow won the max. Start at the winner of max(sold[n], rest[n]) and follow those arrows back to day 0. An arrow rest → hold is a buy, hold → sold is a sell, sold → rest is the cooldown day. When prices only fall, rest wins every day and the path never leaves it (Demo: falling prices 7 6 4 3 1).

Changing the rules means changing the arrows

The same table solves the other classic variants. Only the arrows change:

RuleChange to the state machine1 2 3 0 21 3 2 8 4 9
Cooldown 1 daysold → rest only38
No cooldownadd sold → hold: hold[i] also tries sold[i-1] − p413
Fee 2 per saleas no cooldown, and the sell arrow is +p − 208

Without the cooldown, 1 2 3 0 2 gives 4: buy at 1, sell at 3, buy at 0 right away, sell at 2 (Demo: no cooldown, same prices). With a fee, small rises stop paying: on 1 3 2 8 4 9, buying at 1 and selling at 3 earns 3 − 1 − 2 = 0. The best is 1 → 8 and 4 → 9: (8 − 1 − 2) + (9 − 4 − 2) = 5 + 3 = 8. Without the fee, three trades would give 13 (Demo: fee 2 per sale).

Three small state machines side by side. Cooldown: sold goes only to rest. No cooldown: an extra arrow from sold to hold labelled buy. Fee 2: the same extra arrow, and the sell arrow is labelled plus p minus 2
Each rule of the problem is one arrow added, removed or relabelled.

Time and space

Each day has three cells, and each cell reads at most three cells of the day before: O(n) time. Since day i needs only day i−1, three variables are enough for the profit: O(1) space. The full table (or the winning arrow of each cell) is only needed to recover the trades.

See also: House Robber is the one-state version (robbed or not, folded into one number); DP on trees also returns two numbers per node (taken / not taken); 0/1 Knapsack is a two-dimensional table with a trace back; and Finite State Machines covers state machines on their own.

What the page leaves out

A limit of k transactions (one more index: the number of trades left, so hold[i][j], rest[i][j]); a single transaction only (the simple "min price so far" scan); holding more than one share or short selling; the top-down memoized version of the same recurrence.