DP XI — State Machine

Review boundary and corrected contracts

For the code below, prices are nonnegative, k is a nonnegative integer, and one share may be held at a time. free[t] is the best cash with at most t completed trades; hold[t] is the best cash while holding, with at most t buys (and at most t−1 sells). Zero initializes every free budget because doing nothing is allowed. Same-day transitions are proved safe below for this no-fee/no-cooldown model; cooldown needs a different state graph.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Turn the stock-trading family from impossible into routine by drawing the state machine on paper before writing any code, then transcribing edges into recurrences mechanically.

Series: LeetCode — From Basics to Production-Ready · Session 43 / 65 · Phase 2 · Dynamic programming

Prerequisites. L33–L35 (state definition, recurrence, memo to table). Familiarity with 1D rolling DP helps but is not required — the arrays here are built from scratch.

Watch first

Optional original video resources (not prerequisites for the worked examples):

• Best Time to Buy and Sell Stock with Cooldown — Leetcode 309 — NeetCode. The three-state variant, which is the smallest problem where drawing the diagram first is obviously cheaper than reasoning in your head.
• Maximum Subarray — Leetcode 53 — NeetCode. Kadane's is the two-state machine in disguise — extend or restart — and it is the gentlest possible entry to the pattern.
• Maximum Product Subarray — Leetcode 152 — NeetCode. Two tracked states (running max and running min) where dropping one silently breaks the answer — the clearest argument for naming your states.

Why this session exists

Drawing the state machine on paper first turns these from impossible to routine. That is not motivational filler — it is a mechanical claim, and this session is about cashing it out.

The stock problems have a reputation for being a confusing family of near-identical variants: with cooldown, with a fee, with at most two transactions, with at most k. People memorise each one separately and then blank when a variant they have not seen appears. That approach does not scale and it is not necessary.

Every one of them is the same object: a small directed graph where nodes are situations you can be in and edges are actions you can take today. Once the graph is on paper, the code is a transcription. Each node becomes an array, each incoming edge becomes a term in a maximum, and the price of the day appears in the edges that involve buying or selling. There is no cleverness left after the drawing step.

The reason this matters beyond stocks is that "explicit named states" is a general escape hatch. Whenever a DP feels stuck because the answer depends on some qualitative condition — did I just take one, am I currently inside a run, have I used my one skip — the fix is to add that condition as a named state rather than trying to encode it into the index arithmetic. Stocks are just the cleanest place to learn the move.

Blank-file warm-up

Five minutes, empty file, no notes. Write the hold[i] and free[i] arrays for unlimited-transaction stock trading:

1. Declare both arrays and state in words what each one means.
2. Write both base cases at i = 0, and be prepared to justify why hold[0] is negative.
3. Write both transitions.

The base case is where people stumble. hold[0] = -prices[0] because to be holding a share on day zero you must have bought it, spending that much cash. If you wrote 0 there, you have allowed yourself a free share and every subsequent answer is inflated.

Pattern anatomy

The shape that summons this pattern: a sequence you traverse once, where at each step your legal actions depend on a small qualitative condition that persists between steps. Holding versus not holding. In cooldown versus free to act. Having used two transactions versus three.

The invariant: for each state s and each index i, dp[s][i] is the best achievable value considering the first i+1 elements and ending in state s. "Ending in state s" is load-bearing — the value is conditional on the state, not a global best. The final answer is the maximum over terminal states, usually the not-holding one.

The mechanical procedure, which I want you to follow literally:

1. List the states. Ask: what do I need to know about the past to decide what is legal today? Each distinct answer is a state. Keep the list small — two or three is typical.
2. Draw an edge for every legal action, including the do-nothing self-loops. Label each edge with what it costs or earns.
3. Write one array per state.
4. For each state, take the maximum over its incoming edges. That is the recurrence, with no further thought required.

For unlimited transactions there are two states — hold (you own a share) and free (you do not) — and four edges. Draw yesterday's two states on the left and today's on the right. Two arrows stay in the same state and change no cash; buying crosses from free to holding and subtracts today's price, while selling crosses from holding to free and adds it. Now read the arrows by destination: the holding cell chooses between staying and buying, and the free cell chooses between staying and selling. Those two pairs of incoming arrows become the two assignments below:

def max_profit_unlimited(prices):
    if not prices:
        return 0
    n = len(prices)
    hold = [0] * n      # best cash if I own a share at the end of day i
    free = [0] * n      # best cash if I own nothing at the end of day i
 
    hold[0] = -prices[0]    # bought today
    free[0] = 0             # did nothing
 
    for i in range(1, n):
        # stay holding, or buy today from a free state
        hold[i] = max(hold[i - 1], free[i - 1] - prices[i])
        # stay free, or sell today from a holding state
        free[i] = max(free[i - 1], hold[i - 1] + prices[i])
 
    return free[n - 1]      # never optimal to end holding

Four edges, four terms, two lines. Now watch the variants fall out without new thinking:

Transaction fee — subtract the fee on the sell edge: free[i] = max(free[i-1], hold[i-1] + prices[i] - fee). One token changed.

Cooldown — you cannot buy the day after a sell, so free splits into sold (sold today) and rest (not holding and ready to buy on the next day). From yesterday's values: new_hold = max(hold, rest - price), new_sold = hold + price, new_rest = max(rest, sold). Start before day zero with hold = sold = -infinity, rest = 0; return max(sold, rest). Updating all three from snapshots blocks a buy on the day immediately after a sale. Three states, five edges, and no self-loop on sold.

At most k transactions — add a transaction-count dimension:

def max_profit_k(k, prices):
    n = len(prices)
    if n < 2 or k == 0:
        return 0
    if k >= n // 2:                       # unlimited regime
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))
 
    hold = [float("-inf")] * (k + 1)
    free = [0] * (k + 1)
 
    for price in prices:
        for t in range(1, k + 1):
            hold[t] = max(hold[t], free[t - 1] - price)   # buy opens txn t
            free[t] = max(free[t], hold[t] + price)       # sell closes txn t
    return free[k]

The k >= n // 2 shortcut matters: with n days there are at most n // 2 disjoint profitable trades, so beyond that the constraint is not binding and the unlimited greedy applies. Without it, k = 10^9 allocates arrays you cannot afford.

The cue

You are looking at a state-machine DP when the statement contains these tells:

1. A sequence plus a persistent binary or small-integer condition. Holding or not. In a cooldown or not. Count of something used so far, bounded by a small number.
2. "At most k" where k is small — 2, 3, or an explicit parameter with a modest bound. That k becomes a dimension, and its smallness is the permission to add it.
3. A restriction that references the previous step, like "cannot buy the day after selling" or "no two adjacent". Any rule mentioning yesterday means yesterday's state must be carried forward.
4. The words "buy", "sell", "cooldown", "transaction", "hold" — the stock family announces itself. But do not stop at pattern-matching the vocabulary; the same shape appears in "maximum sum with no two adjacent" and "delete and earn".
5. You tried a single 1D array and could not write the transition because whether an action is legal depends on something the array does not record. That failure is itself the cue: the missing information is your second state.

Tell 5 is the one that generalises beyond stocks. When a DP feels one dimension short, it usually is, and the missing dimension is qualitative rather than positional.

Guided solve

Best Time to Buy and Sell Stock IV — at most k transactions, one share at a time, must sell before buying again. Maximise profit.

Draw before you code. Two base states — holding and free — crossed with "how many transactions have I opened so far", giving 2(k+1) states in total. That is the whole model.

Now the convention decision, and this is where most implementations go wrong. Does a transaction count when you buy, or when you sell? Either works, but you must pick one and be consistent. I count on buy: opening a position increments the counter. So hold[t] means "I own a share and have opened at most t transactions", and free[t] means "I own nothing and have completed at most t transactions". These are budget states, not exact counts. For exact counts, only free[0] would start at zero; other free states would start at negative infinity.

With that convention the edges write themselves:

• To reach hold[t]: either you were already there yesterday and did nothing, or you were at free[t-1] and bought today, paying price.
• To reach free[t]: either you were already there, or you were at hold[t] and sold today, earning price.

Note that selling does not change t under this convention, because the transaction was already counted at the buy.

Base cases: free[t] = 0 for all t — at most t completed transactions permits doing nothing. hold[t] = -infinity initially, meaning "not yet reachable". Using negative infinity rather than zero is important: it prevents the algorithm from believing it can be holding a share for free before any day has been processed.

The ascending in-place loop reads today in two places: free[t] reads new hold[t], and the next hold[t+1] reads new free[t]. A same-day buy then sell has zero profit and can be removed. A same-day sell then buy at the same price can be replaced by holding through the day, using no more transactions. Removing these pairs turns an in-place path into a legal schedule with the same cash and no greater budget. This proves optimum equality, not equality to an exact-count yesterday-only table.

Trace k = 2, prices = [3, 2, 6, 5, 0, 3]. The answer is 7: buy at 2, sell at 6 for 4, then buy at 0, sell at 3 for 3. Watch hold[1] climb to -2 on day two and free[1] reach 4 on day three, then hold[2] reach 4 - 0 = 4 on day five and free[2] reach 7 on day six.

The uncompressed recurrence reads yesterday. The displayed in-place arrays may read today too, effectively allowing zero-profit same-day transitions. For this no-fee/no-cooldown, at-most-k objective that cannot improve the optimum beyond a legal schedule. Use snapshots for variants where this equivalence fails.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Best Time to Buy and Sell Stock with Transaction Fee — one token different from the unlimited version. The only real decision is whether to charge the fee on buy or on sell; pick one and be consistent, and think about whether the answer differs.
• Best Time to Buy and Sell Stock III — at most two transactions. You can either instantiate the general k solution with k = 2, or write four explicit named variables. Do it with four named variables first; the naming forces you to say what each state means.

If both land early, do Best Time to Buy and Sell Stock with Cooldown and draw the three-state diagram before writing a line.

Common failure modes

hold initialised to 0 instead of negative infinity or -prices[0]. This grants a free share and inflates every answer. It often still passes the first sample, which is the worst kind of bug.

Inconsistent transaction counting. Incrementing t on both buy and sell halves your effective k. Incrementing on neither makes k meaningless. Write the convention in a comment before the loop.

Missing the k >= n // 2 shortcut. With k up to a billion, allocating k + 1 slots is an instant memory failure. The shortcut is three lines and it is the difference between accepted and crashed.

Changing the counting convention without changing the edges. Counting on buy reads free[t-1] when buying; counting on sell instead increments on the sell edge. Merely allowing a same-price round trip does not create profit in this model, regardless of loop direction. A cooldown violation is different: using yesterday's just-sold cash to buy today illegally yields 4 on [1, 2, 3, 0, 2], while the legal optimum is 3. Derive the state and allowed edges before choosing update order.

Returning hold[k] alone. With nonnegative prices, dropping an unmatched final purchase cannot reduce cash, so free[k] dominates hold[k]. Returning only hold can be too small (one price [5] gives −5 for a holding state versus 0 when free), though zero-price cases can tie. Returning max(free[k], hold[k]) is redundant, not wrong, under this contract.

Myth: For the two-transaction problem you can just run the single-transaction algorithm twice — find the best trade, remove those days, then find the best trade in what remains.

Why: On [1, 5, 2, 8], the best single trade is buy at 1 and sell at 8 for 7. Removing its endpoint days leaves [5, 2], with no profit. But two legal trades buy at 1/sell at 5 and buy at 2/sell at 8 earn 4 + 6 = 10, not 7. Keeping a greedy trade that straddles the optimal split loses the better pair. The state machine retains the best result for each budget rather than committing to one trade first.

Steps 1: Because you may hold at most one share, your position on any day is fully described by a single bit: holding or not holding.

Steps 2: Because a transaction limit constrains the future, the count of transactions used so far must also be part of the state.

Steps 3: Because those two pieces together determine which actions are legal today, and nothing else about the past does, the pair (holding, count) is a sufficient state.

Steps 4: Because each state has a bounded number of incoming edges — do nothing, or perform the one legal action — each cell is a maximum over at most two terms.

Steps 5: Because there are n days and 2(k+1) states with constant work each, the total is O(n·k).

Steps 6: The general branch performs n·k state updates; the large-k branch makes one pass. This predicts operation counts, not a measured ramp followed by a flat runtime curve: crossing the shortcut threshold can sharply reduce the work.

Picture: A subway map with two or three stations. You are always standing at exactly one station. Each day a train departs on every outgoing line, and each line has a fare written on it — negative to buy, positive to sell, zero to stay put. You want the route through n days that maximises your money, and you track the best possible balance at each station on each day.

Trigger: Fires when your legal moves today depend on a qualitative fact about yesterday, and a plain 1D array has nowhere to record that fact.

Name: Explicit named variables per state

Gain: Self-documenting — hold1, sold1, hold2, sold2 read like the diagram; almost impossible to index wrong; fastest to write for k = 2

Cost: Does not generalise — you cannot write 2(k+1) named variables for arbitrary k, and adding a state means rewriting everything

Name: Arrays indexed by transaction count

Gain: Handles any k with the same code; collapses cleanly to O(k) space; one loop covers all variants

Cost: The counting convention becomes a silent correctness hazard, and the in-place update needs a justification you must be able to give

Pick: Use named variables when the number of states is fixed and small — Stock III with k = 2, or the three-state cooldown machine. Switch to indexed arrays the moment k is a parameter of the input rather than a constant in the problem statement.

Memory hook — "draw the nodes, then transcribe the arrows"

The whole method is two steps and the peg is that you are never allowed to skip the first one.

Nodes are situations, not positions. Ask: at the end of a day, what qualitatively different circumstances can I be in? For unlimited stock trading there are two — holding or free. With cooldown there are three — holding, free and allowed to buy, free but resting. With at most k transactions there are 2(k+1). Name each node in English before you name any variable.

Arrows are today's actions. Every arrow into a node becomes one term inside a max. An arrow that costs money subtracts today's price; an arrow that earns money adds it; a do-nothing self-loop contributes the node's own previous value. The peg: "one array per node, one term per incoming arrow."

That pairing is the mnemonic in full: nodes become arrays, arrows become terms. There is no third step. If you can draw the diagram you can write the code, and if you cannot draw the diagram no amount of index arithmetic will save you.

The base-case peg is separate: "unreachable is negative infinity, not zero." A state you cannot legally be in on day zero must be seeded with negative infinity, because zero silently grants a free share and inflates every downstream answer. This is the single most common bug in the family.

What reviewers actually ask

The stock family is asked constantly because the variants form a natural escalation ladder inside one problem statement — a reviewer can start easy and keep going for the whole session without ever changing context.

• 121 · Best Time to Buy and Sell Stock (Easy) — Practice selection. One transaction. Probing whether you avoid the O(n^2) pair scan. Follow-up: immediately escalates to 122.
• 122 · Best Time to Buy and Sell Stock II (Medium) — Practice selection. Unlimited transactions. Probing the two-state machine, or the greedy "sum every positive difference" shortcut. Follow-up: "prove the greedy is correct" — the state machine is the proof.
• 309 · Best Time to Buy and Sell Stock with Cooldown (Medium) — Practice selection. Probing whether you add a third node rather than hacking an index offset.
• 714 · Best Time to Buy and Sell Stock with Transaction Fee (Medium) — Practice selection. Probing consistency: charge the fee on buy or on sell, but exactly once per round trip.
• 123 · Best Time to Buy and Sell Stock III (Hard) — Practice selection. At most two transactions. Probing whether you can name four explicit states without confusing them.
• 188 · Best Time to Buy and Sell Stock IV (Hard) — Practice selection. The general k. Probing the generalisation plus the large-k shortcut: when k >= n / 2 it collapses to the unlimited case.
• 53 · Maximum Subarray (Medium) — Practice selection. Kadane's as extend-or-restart. Follow-up: 152 · Maximum Product Subarray, which needs a second tracked state because a negative times a negative flips the winner.

The escalation pattern is worth internalising on its own: 121 to 122 to 309 to 123 to 188, each adding one node or one axis. If you have the drawing habit, that ladder costs you nothing; if you memorised five separate solutions, it ends you at the fourth rung.

Complexity

Time: O(n·k) for the general version — n days times 2(k+1) states, constant work per state. With the k >= n // 2 shortcut the effective bound is O(n·min(k, n)) which is O(n²) worst case, but in the regime where the shortcut fires the actual work is a single O(n) pass.

Space: O(k) with the collapsed form, or O(n·k) if you keep the day dimension. The collapse is valid because each state on day i reads only day i-1 values, plus same-day values whose reuse provably cannot improve the answer.

Unlimited transactions: O(n) time, O(n) space in the displayed arrays; O(1) with scalars — two scalars, no arrays needed at all. The greedy sum of positive daily differences is the same algorithm in disguise, which is worth verifying for yourself as an exercise.

You can now…

• Recognise the pattern when an answer depends on a qualitative condition rather than only on position.

• Draw the state diagram before writing code, naming each node as an English situation.

• Transcribe the diagram mechanically — one array per node, one max term per incoming arrow.

• Seed unreachable states with negative infinity and justify why zero is wrong.

• Pick a buy-or-sell convention for counting transactions and hold it consistently through the whole solution.

• Collapse the day dimension to O(1) or O(k) memory and explain why the in-place same-day read is safe.

• Walk the escalation ladder from one transaction to unlimited to cooldown to fee to at-most-k without memorising five solutions.

Quiz

Self-check (answer follows each question).

Q: Why is hold[0] initialised to -prices[0] rather than 0?

A: To be holding a share at the end of day zero, you must have bought it, which costs cash. Initialising to 0 grants a free share and inflates every downstream value.

Q: In the k-transaction loop, why is it safe that free[t] reads the freshly updated hold[t] from the same day?

A: It permits buying and selling on the same day, which nets exactly zero profit and therefore can never beat the alternative of doing nothing. Harmless, and it saves a second copy of the arrays.

Q: What does the k >= n // 2 shortcut do and why is it correct?

A: It falls back to the unlimited-transaction greedy. With n days there can be at most n/2 disjoint profitable trades, so any k beyond that is not a binding constraint. Without it, a large k causes an unaffordable allocation.

Q: How does the cooldown variant change the state machine?

A: The free state splits into two: just-sold-today (cooldown) and free-to-buy (rest). The buy edge originates only from rest, and the cooldown state transitions into rest after one day.

Q: Why return free[k] rather than max(free[k], hold[k])?

A: Ending while holding a share means you spent cash and never recovered it, which is dominated by simply not buying. hold[k] can never exceed free[k] at the final index.

Q: Give a non-stock problem with the same shape and identify its states.

A: House Robber: the states are 'robbed the current house' and 'skipped the current house', since the restriction references the previous step. Or Delete and Earn, which reduces to House Robber over value counts. Any 'no two adjacent' rule is a two-state machine.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Log the stock variants as separate entries. They feel like one problem after this session, but retrieval is per-variant until you have drawn each diagram at least twice.

• Draw the state machine on paper before writing code. Nodes are situations, edges are actions, and the code is a transcription.

• Two states plus a transaction budget cover the no-cooldown family. Cooldown must distinguish just-sold from ready-to-buy, or retain equivalent delayed history.

• Initialise hold to negative infinity or -prices[0]. Zero grants a free share and silently inflates the answer.

• Pick whether a transaction counts on buy or on sell, write it in a comment, and never waver.

• The k >= n // 2 shortcut is mandatory when k is unbounded in the constraints.

• When a 1D DP feels one dimension short, the missing dimension is usually qualitative — name it as a state.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.