State-Machine DP · bigonotes

Some problems put you in one of a few modes at every step: holding a stock or not, in a cooldown or not, on an up-step or a down-step. State-machine DP keeps one best value per mode and updates all of them as you read each element. The stock buy/sell series is the standard family, and each variant adds or changes a state.

The idea#

Name the states and draw the allowed moves between them for one day. With a one-day cooldown after each sale there are three:

State	Meaning	Reached from
`hold`	you own a share	`hold` (keep it) or `rest` (buy today: `- price`)
`sold`	you sold today	`hold` (sell today: `+ price`)
`rest`	no share, free to buy	`rest` (wait) or `sold` (the cooldown day)

Each day, compute the new value of every state from yesterday's values, then move on. This is correct because the future depends only on which mode you're in and how much money you have, not on the exact trades that got you there. The answer is the best of the states where you don't hold a share.

How to spot it#

Look for these signals in the question.

A small set of modes that the problem's rules switch between (holding, cooldown, transactions used, last direction).
Rules like "must sell before you buy again", "one day cooldown after selling", "fee per transaction", "at most k transactions".
A single pass over the input where each step's choice depends on the current mode.

Template#

The shape is the same for every member of the family. Only the list of states and their "reached from" rules change.

start each state at its value before day 1
    (a state you can't be in yet starts at -infinity)
for each element x:
    for each state s, using only yesterday's values:
        new[s] = best over the moves into s
                 (stay in s, or come from t with a gain or cost)
    replace every state with new, all at once
return the best of the states that are valid at the end

This is one pass with a fixed number of states, so it runs in $O(n)$ time and $O(1)$ space.

Trace with the cooldown states#

To see the template run, here are the three cooldown states from the table above on prices [1, 2, 3, 0, 2], starting from hold = -inf, sold = 0, rest = 0:

day	price	hold	sold	rest
1	1	-1	-inf	0
2	2	-1	1	0
3	3	-1	2	1
4	0	1	-1	2
5	2	1	3	2

The answer is 3: buy at 1, sell at 2, cool down, buy at 0, sell at 2.

Pitfalls#

These mistakes cause the most wrong answers.

Updating states one at a time so a later line reads today's value instead of yesterday's. Use a tuple assignment or temporaries.
Starting hold at 0. You can't hold a share before buying one; use -inf (or -prices[0]).
Charging a per-transaction cost twice. A transaction is a buy plus a sell, so charge it once.
Running a general DP when a limit is so large it no longer binds. Check whether the problem collapses into a simpler case.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Best Time to Buy and Sell Stock

One trade only. Track two values: the cheapest price so far and the best profit so far.

Hint: Best Time to Buy and Sell Stock II

No states needed: sum every positive daily change. Any trade from day b to day s is a telescoping sum of daily changes. With unlimited trades you choose which changes to include, and one-day trades never overlap. Adding a positive change always helps; adding a negative one always hurts.

Hint: Best Time to Buy and Sell Stock with Cooldown

Use the three states hold, sold and rest from the table. hold comes from rest - price, not from sold - price: that is the cooldown. Return max(sold, rest).

Hint: Best Time to Buy and Sell Stock with Transaction Fee

Two states, hold and cash. Subtract the fee once, on the sell: cash = max(cash, hold + price - fee).

Hint: Best Time to Buy and Sell Stock III

Four states: buy1, sell1, buy2, sell2. Each sell feeds the next buy, so buy2 comes from sell1 - price.

Hint: Best Time to Buy and Sell Stock IV

Keep buy[t] and sell[t] for each t ≤ k. If k ≥ n / 2, the limit never binds and this is the unlimited case.

Hint: Longest Turbulent Subarray

Keep two states: up (longest turbulent run ending here on an up-step) and down. An up-step extends the previous down run, and a down-step extends the previous up run. Equal neighbors reset both to 1. Like Kadane's algorithm, each position carries the old run or starts fresh.

Key takeaways#

Name the modes, then write each one's value from yesterday's values.
Update all states together.
The answer comes from the states where you hold nothing.
More rules mean more states, not a different algorithm.

Core idea#

At every step you are in one of a few modes: holding a stock or not, in a cooldown or not. Keep one best value per mode, and update all of them as you read each element.

Key points#

Name the states and the allowed moves between them for one day.
Compute each state's new value from yesterday's values.
The future depends only on the mode and the money, not on the exact trades.
The answer comes from the states where you hold nothing.
More rules mean more states, not a different algorithm.
Spot it: "sell before you buy again", "cooldown", "fee per transaction", "at most k transactions".
Cooldown states: hold (keep, or buy from rest), sold (sell from hold), rest (wait, or come from sold).

The stock series#

Problem	States	Key idea
One trade	`min price`, `best profit`	Track the cheapest price so far
Unlimited	none	Sum every positive daily change
Fee	`hold`, `cash`	Subtract the fee on sell
Two trades	`buy1`, `sell1`, `buy2`, `sell2`	Each sell feeds the next buy
`k` trades	`buy[t]`, `sell[t]`	If `k ≥ n / 2`, it is the unlimited case

Longest Turbulent Subarray uses two states, up and down. An up-step extends the previous down run, and equal neighbors reset both.

Template#

hold = -infinity; sold = 0; rest = 0
for each price p:
    # all three read yesterday's values: update together
    new_hold = max(hold, rest - p)    # keep, or buy after rest
    new_sold = hold + p               # sell today
    new_rest = max(rest, sold)        # wait, or cooldown day
    hold, sold, rest = new_hold, new_sold, new_rest
return max(sold, rest)
fee version: hold, cash; cash = max(cash, hold + p - fee)

Pitfalls#

Updating states one at a time, so a later line reads today's value. Use a tuple assignment.
Starting hold at 0. Use -inf or -prices[0].
Charging the fee on both buy and sell. Charge it once per transaction.
Running the full k-transaction DP when k ≥ n / 2.

Say it in an interview#

"Three states: hold, sold and rest. Each day's values come from yesterday's."
"With unlimited trades, any trade is a sum of daily changes, so take every positive one."