L43 · DP XI — State Machine

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

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:

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 two states: cooldown (just sold today) and rest (free and able to buy). The buy edge now originates only from rest. Three states, five edges, still a direct transcription.

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 currently own a share and this is my t-th transaction", and free[t] means "I own nothing and I have completed t transactions".

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 — completing zero-profit transactions is always achievable by 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 in-place update in the loop deserves a comment because it looks like a bug. Inside the day loop, hold[t] is updated first and then free[t] reads the new hold[t]. That permits buying and selling on the same day, which yields exactly zero profit and therefore never improves the answer — it is harmless, and it saves you from maintaining two copies of every array. Say this out loud in an interview; noticing it and explaining why it is safe reads as care rather than luck.

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.

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.

Iterating transactions in the wrong direction with the space-optimised form. If you count on sell instead of buy, the in-place update may read a value from the current day that is not safe, permitting a same-day round trip that does produce profit. Check which index the buy edge reads: it must be t-1 if t is incremented on buy.

Returning hold[k] instead of free[k]. Ending while still holding a share is never optimal, since you could always have not bought it. Returning the holding state gives an answer that is too low by roughly one share price.

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(1) space — 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.

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.