State Machine DP applies when a problem can be modeled as a sequence of states with defined transitions. Instead of thinking in terms of indices alone, you track the current state and how it evolves based on each decision.

This pattern shows up whenever a problem restricts how you can move between different phases or statuses. The stock trading problems on LeetCode are the canonical example, but the idea extends to other problem families as well.

In regular DP problems like climbing stairs or coin change, you track a single thing: the position you are at or the amount remaining. The state is a single number.

State machine DP adds another dimension. At each step, you are not only at position i, you are also in a particular mode or status. The same position can have different optimal values depending on the mode.

For example, in a stock trading problem, being on day 5 while holding a stock is a different state from being on day 5 with no stock. These are two separate states, even though the day is the same.

The core components of state machine DP are:

State machine DP differs from regular DP in this way: regular DP has one recurrence relation, while state machine DP has one recurrence relation per state, and they reference each other.

Not every DP problem needs a state machine. The signals that point to this pattern:

The common thread is that the problem maps to "I am in state X, and from here I can go to state Y or Z." If the problem distinguishes between modes (holding vs not holding, etc.), state machine DP is the pattern.

The recipe for state machine DP:

Apply this to the stock problem family. The simplest version, Buy and Sell Stock with unlimited transactions, has two states (held and notHeld) with buy and sell arrows between them. The recurrences are immediate:

The variants in the table above all reuse this template; the diagram changes, the recipe does not.

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You can complete as many transactions as you like (buy one, sell one, buy one, sell one, ...) with the following constraint: after you sell, you must wait one day before buying again (cooldown period). You cannot hold multiple shares at once. Find the maximum profit.

Setting Up The States

Without the cooldown, you could buy and sell greedily. The mandatory rest day after selling means you sometimes want to delay selling or skip a profitable opportunity to set up a better one.

This maps to three states:

Reading directly from the diagram, the recurrence relations are:

Step-by-Step Trace

Trace prices = [1, 2, 3, 0, 2].

Base cases (day 0, price = 1):

Applying the recurrences day by day:

The answer is max(sold[4], rest[4]) = max(3, 2) = 3.

The optimal strategy that achieves profit 3: buy on day 0 at price 1, sell on day 1 at price 2 (profit 1), cooldown on day 2, buy on day 3 at price 0, sell on day 4 at price 2 (profit 2). Total = 3.

The greedier-looking plan "buy day 0, sell day 2 for profit 2, then buy day 3 and sell day 4" fails because selling on day 2 forces cooldown on day 3, so day 3 cannot be a buy day. The state machine handles this without extra bookkeeping: held[3] = 1 is reached via rest[2] - prices[3] = 1 - 0, where rest[2] = 1 came from sold[1] = 1 flowing through the cooldown, not from a sell on day 2.

Implementation

Complexity Analysis

This is the most general stock state machine and the standard case for adding a transaction-count dimension. You are given an array prices and an integer k. Complete at most k buy-sell transactions, holding at most one share at a time, and return the maximum profit.

Why A Third Dimension

The earlier variants used two or three states per day (held vs notHeld, or held / sold / rest). When the number of allowed transactions is bounded, day-plus-holding is no longer enough state: two histories that arrive at the same day in the same holding state might have used different numbers of transactions, and only one of them might still have transactions left.

The state grows to three dimensions:

A transaction is counted at the moment of buying. Selling completes a transaction that was already counted; it does not consume a new one.

Recurrence

Not holding, day i, j transactions used:

dp[i][j][0] = max( dp[i-1][j][0], // rest, do nothing

dp[i-1][j][1] + prices[i] ) // sell what we held

Holding, day i, j transactions used:

dp[i][j][1] = max( dp[i-1][j][1], // keep holding

dp[i-1][j-1][0] - prices[i] ) // buy, consuming one transaction

The j - 1 on the buy transition is the bookkeeping that makes this work: holding a stock today with j transactions used means yesterday we had j - 1 transactions used and were not holding, then we bought.

Base Cases

Answer

max over j in [0, k] of dp[n-1][j][0]. The final state must not be holding; any leftover holding cannot be cashed out.

Special Case: k Is Large

LC 188 allows k up to 10^9. When k >= n / 2, the transaction budget is effectively unlimited: there are at most n / 2 non-overlapping buy-sell pairs in n days, so allocating more does not help. Fall back to the unlimited-transactions formula: sum of all positive consecutive price deltas. Without this early exit, allocating a (n+1) x (k+1) x 2 table runs out of memory.

Implementation

Sanity Check

For prices = [3, 2, 6, 5, 0, 3], k = 2, the optimal plan is buy at 2, sell at 6 (profit 4), then buy at 0, sell at 3 (profit 3). Total 7. Tracing the DP arrays day by day reproduces sell[2] = 7 on the final day.

Complexity Analysis

Without the k >= n / 2 bailout, the worst-case complexity would be O(n * k) with k = 10^9, which is infeasible.

How The Variants Compare

The four buy/sell variants in this chapter share a single template and differ only in which transition is allowed:

The general recipe is: draw the state diagram, label each transition with what it adds to the profit (or subtracts), and apply the bookkeeping for any constraints that require additional state dimensions.