State Machine DP

State Machine DP

Some DP problems are easiest to think about as a small set of situations you can be in, plus rules for moving between them each step. "Today I'm holding a stock, or I'm not holding one, or I just sold and must wait a day." Each situation is a state. For every step (day, house, character) you track the best result achievable if you end that step in each state. That's state machine DP.

The method is always the same:

1. List the states you could be in after a step.
2. Draw the transitions: which states can lead to which, and what each move gains or costs.
3. For each step, compute best[state] = max (or min) over every transition into that state.
4. The answer is the best among the valid final states.

Because each step only depends on the previous step, the whole table usually collapses to a few variables: O(n) time and O(1) space.

The stock problems: one family, different state machines

All versions share the input prices[i] (price on day i) and the goal of maximizing profit. What changes is the rules, and therefore the states.

One transaction

Only one buy and one sell. No state machine is needed yet: track the cheapest price seen so far and the best profit from selling today.

int maxProfitOne(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        best = Math.max(best, p - minPrice);
    }
    return best;
}

Unlimited transactions: two states

            buy (−price)
   ┌──────┐ ─────────────▶ ┌──────┐
   │ FREE │                │ HOLD │      stay in either state = do nothing today
   └──────┘ ◀───────────── └──────┘
            sell (+price)

• hold = the best profit so far if I own a share at the end of today.
• free = the best profit so far if I don't own one.

int maxProfitUnlimited(int[] prices) {
    int hold = -prices[0], free = 0;              // day 0: either bought, or did nothing
    for (int i = 1; i < prices.length; i++) {
        int newHold = Math.max(hold, free - prices[i]);   // keep holding, or buy today
        int newFree = Math.max(free, hold + prices[i]);   // stay out, or sell today
        hold = newHold;
        free = newFree;
    }
    return free;                                   // ending while holding is never better
}

Computing both new values from the old ones before assigning avoids subtle bugs. Here it happens not to matter, but in the next variant it does.

With a one-day cooldown after selling: three states

FREE ──buy──▶ HOLD ──sell──▶ COOLDOWN ──(next day)──▶ FREE
 ↺ rest        ↺ keep

int maxProfitCooldown(int[] prices) {
    int hold = -prices[0], cooldown = 0, free = 0;
    for (int i = 1; i < prices.length; i++) {
        int newHold     = Math.max(hold, free - prices[i]);   // can only buy from FREE, not from COOLDOWN
        int newCooldown = hold + prices[i];                   // sold today → forced rest tomorrow
        int newFree     = Math.max(free, cooldown);           // rested, or the cooldown ended
        hold = newHold; cooldown = newCooldown; free = newFree;
    }
    return Math.max(free, cooldown);
}

The only difference from the unlimited version is the extra state the rules require. This is the pattern's big advantage: new rules become new states or edges, not new algorithms.

With a transaction fee

The same two states as unlimited. Subtract the fee on sell: newFree = max(free, hold + price − fee).

At most k transactions

The state now also needs how many transactions have been used: hold[t] and free[t] for t = 1..k. Count a transaction when you buy:

int maxProfitK(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;
    if (k >= n / 2) return maxProfitUnlimited(prices);     // k can't be the binding limit

    int[] hold = new int[k + 1], free = new int[k + 1];
    Arrays.fill(hold, Integer.MIN_VALUE / 2);              // "impossible" without risking overflow
    for (int p : prices) {
        for (int t = k; t >= 1; t--) {                     // high → low so t-1 still holds yesterday's value
            free[t] = Math.max(free[t], hold[t] + p);           // sell the t-th transaction
            hold[t] = Math.max(hold[t], free[t - 1] - p);       // buy starts the t-th transaction
        }
    }
    return free[k];
}

O(n × k) time and O(k) space. "At most 2 transactions" (Stock III) is this with k = 2, often written with four named variables: buy1, sell1, buy2, sell2.

Beyond stocks

The same thinking applies whenever "what I did last" restricts "what I can do now".

Paint House: each house gets one of 3 colours, with no two neighbours the same, at minimum cost. The state is the colour of the current house:

int minCost(int[][] cost) {                         // cost[i][c]
    int r = cost[0][0], g = cost[0][1], b = cost[0][2];
    for (int i = 1; i < cost.length; i++) {
        int nr = cost[i][0] + Math.min(g, b);        // red now → previous was green or blue
        int ng = cost[i][1] + Math.min(r, b);
        int nb = cost[i][2] + Math.min(r, g);
        r = nr; g = ng; b = nb;
    }
    return Math.min(r, Math.min(g, b));
}

House Robber is a two-state machine (robbed this house / didn't). Binary strings without consecutive 1s has states "last digit was 0" and "last digit was 1". Regex and wildcard matching can be viewed as state machines over pattern positions.

How to design the states

• Ask: "To decide what's allowed next, what's the minimum I must remember about the past?" That information is the state. Everything else can be forgotten.
• Too few states means you can't enforce a rule. Too many means wasted work, so merge states that allow exactly the same future moves.
• Draw the diagram before coding. The transitions are the recurrence.
• Initialize impossible states to −∞ (for maximization) or +∞ (for minimization), and use a safe sentinel like MIN_VALUE / 2 so that adding to it can't overflow.

Follow-up questions this topic invites — and their answers

Q: Why use temporary variables when updating the states? A: Each new state must be computed from the previous step's values. Updating one state in place and then using it to compute another mixes today's and yesterday's values. In the cooldown version, that would allow buying on the same day you sold.

Q: Why does k >= n/2 reduce to the unlimited case? A: A profitable transaction needs at least two days (buy, then sell later), so there can never be more than n/2 useful transactions. If k is at least that, the limit never binds, and the O(n) unlimited solution is exact.

Q: How do you reconstruct the actual trades, not just the profit? A: Keep the full per-day state table (or record which transition won at each step), then walk backwards from the best final state, following the recorded choices. That needs O(n × states) space instead of O(states).

Q: How is state machine DP different from ordinary DP? A: It's the same technique. It just emphasizes that the DP index is (step, state), with a small fixed set of states and explicit transitions. Thinking in states makes rule changes (cooldowns, fees, limits) mechanical to handle.

Q: For the k-transactions problem, why iterate t from high to low? A: hold[t] uses free[t − 1] from the same day. Iterating t downwards means free[t − 1] hasn't been updated yet in this round, so it still represents the state before today's sell. That prevents buying and selling within the same day as two different transactions.