State-Machine DP (Stock Trading & Beyond)

The recognition signal

State-Machine DP is the pattern for problems where, at each step, you are in exactly one of a small, fixed number of named modes — and the allowed transitions between modes (not just a numeric index) are what constrain your choices. The tell: you find yourself narrating a solution with sentences like "if I'm currently holding a stock, I can either sell it or keep holding it; if I'm not holding anything, I can either buy or do nothing" — that's you describing states and transitions out loud, which means you should immediately go define them explicitly rather than trying to cram the logic into a single dp[i] array.

This is a distinct skill from the 1-D DP in the DP Foundations subtopic: there, dp[i] meant one thing. Here, you need dp[i][state] — one value per state, per position — because the same index i can have a genuinely different best answer depending on which mode you're in when you arrive there.

The general framework

1. Enumerate the states explicitly, and name them. Don't jump to dp[i][0] and dp[i][1] — first write out, in words, what each mode means: "holding," "not holding," "in cooldown," "just used my kth transaction," etc. This is the state-machine equivalent of the one-sentence state definition from DP Foundations, and it's just as non-negotiable: if you can't name your states in plain language, your transitions will be wrong.
2. Draw (or describe) the transition diagram. For each state, what actions are legal, and which state does each action lead to? This is literally a finite-state machine (states + labeled transitions) — the same conceptual object used to model regexes, protocol handshakes, and parsers, just applied to a sequential decision problem instead of a string.
3. Write one recurrence per state, each in terms of the previous step's states: dp[i][state] = best(all ways to arrive at state from step i-1).
4. The final answer is typically the best value across all "terminal-acceptable" states at the last step (often "not holding anything" — you can't profit from a stock you still own but haven't sold).

Worked shape: holding vs. not holding

The archetypal state-machine DP problem — generalizing the entire stock-trading problem family without spoiling any specific one of your listed problems — has exactly two core states at each day i:

• hold[i] — the best profit achievable through day i, given that you are currently holding one unit of the asset.
• free[i] — the best profit achievable through day i, given that you are currently holding nothing.

Read the two transition lines as literal sentences: "to be holding today, I was either already holding yesterday and did nothing, or I was free yesterday and bought today." "To be free today, I was either already free yesterday and did nothing, or I was holding yesterday and sold today." Writing the recurrence as an English sentence first, then translating directly to code, is what keeps state-machine DP tractable under interview pressure — attempting to jump straight to array indices without narrating the transition in words is where most candidates get stuck.

Extending the base framework

Every variant in the stock-trading family (and most state-machine DP problems generally) is this same two-state skeleton with one added constraint, which manifests as either an extra state or an extra dimension:

Added constraint	How it changes the state machine
A mandatory delay after a particular action (e.g. can't immediately re-enter after exiting)	Add a third explicit state ("just exited, must wait one step") sitting between "holding" and "free," so the delay is enforced structurally by the transition graph rather than by extra bookkeeping
A per-transaction cost	Subtract the cost at the moment you'd otherwise gain value (typically the "sell" transition) — the two-state skeleton itself is unchanged
A cap on the number of transactions allowed	Add a dimension tracking transactions-used-so-far to each state (hold[i][t], free[i][t]), turning two 1-D arrays into two 2-D arrays
A cap that's large relative to the input size	Recognize that once the cap exceeds roughly half the input length, it can never be a binding constraint — collapse back to the unlimited-transactions two-state version, which is asymptotically faster

The lesson generalizes well beyond stock trading: any time a new constraint shows up, ask "does this need a new named state, or just an extra dimension on my existing states?" A delay/cooldown is a new mode (you're not simply "free," you're "free-but-waiting") — a transaction limit is a new dimension on modes you already have (holding-with-2-left, free-with-2-left, etc.).

Comparison: implicit index DP vs. explicit state-machine DP

	1-D DP (Foundations)	State-Machine DP
What dp[i] alone tells you	The complete answer at position i	Nothing by itself — you need dp[i][state]
Number of values tracked per step	1	One per named state (typically 2–4, or more with an added dimension)
How transitions are found	Direct recurrence from choices at step i	Narrate legal transitions between named modes, then translate
Risk if you skip explicit naming	Minor — the recurrence is usually simple enough to hold in your head	High — conflating states (e.g. forgetting "just sold" is different from "free and able to buy") silently produces wrong transitions

Complexity

For n steps and a constant number of states (2–4, as in the two-state or cooldown variants): O(n) time and O(1) space if you keep only the previous step's state values in scalars (exactly like the rolling-array optimization from DP Foundations — the state-machine values are your rolling window, one scalar per state). Adding a transaction-count dimension of size k multiplies both time and space by k, giving O(n·k) time and O(k) space (per-step, rolling) or O(n·k) space if you keep the full history.

Common pitfalls

• Conflating two genuinely different states into one. The most common version: treating "just sold, in a mandatory cooldown" as the same as "free and able to act." If the problem has any delay/cooldown constraint, these are not the same state, even though both involve "not currently holding anything" — collapsing them silently permits illegal actions.
• Wrong base case / initial state values. At step 0, states that are logically impossible (e.g. "holding" before you've had a chance to buy) should be initialized to -infinity (for a maximization problem) so they can never win a max() comparison — initializing them to 0 instead makes an impossible state look like a free, valid option.
• Updating states in the wrong order within a single step. If a later state's transition in your code accidentally reads an already-updated value for the current step instead of the previous step's value, you've effectively allowed two actions (e.g. buy and sell) to happen "simultaneously" on the same day. Always snapshot the previous step's values into temporaries before overwriting.
• Forgetting that the final answer is a max/min over multiple states, not just one. The best profit at the end isn't always "free" by definition in every variant — think through which terminal states are actually valid answers before assuming.
• Reaching for a transaction-count dimension when a large cap doesn't need one. Adding a k dimension you don't need makes the solution slower and more error-prone than the simpler unlimited-transaction skeleton; always check whether the cap can bind at all given the input size first.