State machine DP — LeetCode patterns

Problem

The input is a sequence (prices by day, numbers to sign), and what you may do at a step depends on a small amount of history: you can only sell if you are holding, you can only buy if you are not in a cooldown. Writing the history out as a list of past choices would be exponential. But the future depends on the past only through the mode you are in now, and there are only a handful of modes. Keep the best value for each mode after each step and the whole thing is a linear scan with a few variables.

Signal	Pattern	Why
"You may not do X right after Y" (cooldown, fee, limit)	One state per mode, and edges that skip the forbidden move	The restriction is exactly a missing edge in the state graph.
"Buy then sell, as many times as you like"	Two states: holding and free	Which day you bought on no longer matters once the price is paid into the holding value.
"At most k transactions"	States indexed by (transactions used, holding)	The counter is part of the mode, so the state count is 2k.
"Assign a sign or choice to each number, count ways to reach a total"	State = running total, value = number of ways	Many choice sequences land on the same total, and only the total affects what comes next.
Each step reads only the previous step's values	Update the variables in one simultaneous assignment	No table is needed, just O(1) space per mode.

Intuition

Think of a tiny board game. You hold a token that sits on one of a few squares, and each day you may move it along allowed arrows, collecting or paying money as you go. The best profit is the best score over all walks of that length that end on a good square. Since a walk's future depends only on the square it is on, the best score reaching each square after day i is all you must remember: any walk that reaches the same square with a lower score can be thrown away.

That is dynamic programming with the square as the state. The recurrence for each square is "the best of the squares that have an arrow into me, plus the money on that arrow". It is easy to see which arrows exist by drawing them, and drawing them also exposes mistakes, such as allowing a buy from the square you reach by selling.

Every legal day is one arrow. The missing arrow from sold straight to hold is the cooldown rule. The diagram scrolls sideways on a narrow screen.

Mechanics

Stock with a cooldown: three modes

Let hold, sold and rest be the best profit after today if you end the day holding a share, if you sold one today, or if you hold nothing and sold nothing today. Each is the best of the arrows into it:

hold = max(hold, rest - price): keep holding, or buy today from the resting mode.
sold = hold + price: sell what you held yesterday.
rest = max(rest, sold): stay idle, or come out of yesterday's sale.

All three right-hand sides read yesterday's values, so compute them together (Python's tuple assignment does this) or the update order will leak today's numbers into today's decisions. The answer is the larger of sold and rest on the last day, since ending while still holding is never better than having sold.

Why is it enough to remember one number per mode? Two histories that end in the same mode face exactly the same future options, so the one with less money is dominated. That is the whole proof, and it is the check to run on any new state design: does the mode decide everything about the future?

Unlimited transactions: two modes

Without a cooldown, selling today and buying today are both fine, so "sold" is not a separate mode. Holding and free are enough: hold = max(hold, free - price) and free = max(free, hold + price) with the old hold on the right. The result equals the sum of every positive day-over-day rise. Both views are correct, and the state machine is the one that keeps working when a fee or a limit is added, where the rises shortcut stops applying.

Adding a counter to the mode

If at most k transactions are allowed, the number used so far joins the mode: states are (used, holding), so about 2k of them, each updated from at most two others. Count a transaction when you buy (or when you sell, but be consistent). The scan is O(n·k) time and O(k) space.

Target sum: the mode is the running total

Give each number a plus or a minus and count the assignments that total the target. After i numbers the only fact that matters is the running sum, so keep a dictionary from running sum to the number of sign choices reaching it. Each number sends every entry to two new entries, sum plus value and sum minus value, and entries landing on the same sum are added together. The final answer is the count stored for the target. The dictionary stays small when the sums are bounded: it can never hold more than twice the total of the numbers plus one keys.

Each column is one day and reads only the column before it. Blue marks the final cell that gives the answer. Negative hold values are the money spent on the share currently owned.

Worked example

Cooldown. Prices 6, 1, 4, 9, 2, 5, 8, 3. Running the three updates gives, per day, the (hold, sold, rest) triples -6, 0, 0; -1, -5, 0; -1, 3, 0; -1, 8, 3; 1, 1, 8; 3, 6, 8; 3, 11, 8; 5, 6, 11. The best profit with a cooldown is 11.

Day	Price	Hold	Sold	Rest
0	6	-6	0	0
1	1	-1	-5	0
2	4	-1	3	0
3	9	-1	8	3
4	2	1	1	8
5	5	3	6	8
6	8	3	11	8
7	3	5	6	11

No cooldown. On the same prices with unlimited transactions the two-mode scan ends at 14, and adding up the rises also gives 14. The three-mode answer is smaller by 3 because the sale on day 3 forces the next day to be idle, which blocks the buy at 2 on day 4.

Target sum. Numbers 2, 3, 1, 4, 2, target 4. The dictionary holds 1, 2, 4, 7, 11, 13 distinct sums after 0 to 5 numbers, and 3 sign assignments land on the target.

Implementation

def max_profit_cooldown(prices):
    hold, sold, rest = float("-inf"), 0, 0
    for price in prices:
        hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
    return max(sold, rest)


def max_profit_unlimited(prices):
    hold, free = float("-inf"), 0
    for price in prices:
        hold, free = max(hold, free - price), max(free, hold + price)
    return free

Variations and edge cases

def max_profit_fee(prices, fee):
    hold, free = float("-inf"), 0
    for price in prices:
        hold, free = max(hold, free - price), max(free, hold + price - fee)
    return free


def max_profit_k(prices, k):
    hold = [float("-inf")] * (k + 1)
    free = [0] * (k + 1)
    for price in prices:
        for used in range(1, k + 1):
            hold[used] = max(hold[used], free[used - 1] - price)
            free[used] = max(free[used], hold[used] + price)
    return free[k]


def count_sign_assignments(nums, target):
    ways = {0: 1}
    for value in nums:
        nxt = {}
        for running, count in ways.items():
            nxt[running + value] = nxt.get(running + value, 0) + count
            nxt[running - value] = nxt.get(running - value, 0) + count
        ways = nxt
    return ways.get(target, 0)

Simultaneous update. Writing three separate statements that each read a variable changed above them silently breaks the cooldown logic. Use one tuple assignment or temporaries.
Initial values. Holding before the first day is impossible, so start it at minus infinity; resting starts at 0. A day-0 sale cannot happen, so its value must not exceed rest.
Empty or one-day input. No prices gives 0, a single price gives 0 (buying and selling the same day earns nothing). The loops above return exactly that.
Where to charge the fee. Charge it on either the buy or the sell, never both.
Negative target. The dictionary version handles any target; the subset-count reduction needs the parity and range check shown in the knapsack page.

Complexity and tradeoffs

Time: O(n times the number of modes). The stock versions are O(n) with two or three modes and O(n·k) with the counter. Target sum is O(n times distinct sums), at worst O(n·S) for total S.
Space: O(1) for fixed modes, O(k) with a counter, O(S) for the sum dictionary.
Baseline. Trying every buy-and-sell schedule is exponential; trying every sign assignment is 2ⁿ.
Versus subset-sum reduction. For target sum the knapsack reduction uses a flat array and is faster in practice; the dictionary is more general and survives variations like "each number may also be skipped".
When it fails. If the future depends on something the mode does not capture, such as which specific day you bought, the state is incomplete and the answer is wrong. Add what is missing to the mode, or the dominance argument breaks.

Problems

The cooldown problem is the one to master: it forces you to draw the arrows. Then redo the unlimited version as a two-mode machine and see that the rises shortcut falls out of it.

Medium

309. Best Time to Buy and Sell Stock with Cooldown NeetCode 150 NeetCode 250
Track three states, holding, just sold and resting, and allow a buy only from the resting state.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

122. Best Time to Buy and Sell Stock II Medium
494. Target Sum Medium

Connections

Read first

Linear DP core

Check yourself

Why can a history that ends in the same mode but with less money be discarded?

Both face the same options from then on, and every later gain or cost is identical for both, so the richer one finishes ahead by at least the same margin.

Why does hold start at minus infinity instead of 0?

A starting value of 0 would mean owning a share for free, so selling it would count as pure profit. Minus infinity says that holding before the first purchase is impossible, so the first real value comes from a buy.

Which arrow encodes the cooldown?

There is none from sold to hold. Sold goes only to rest, so the earliest next purchase is two days after a sale. In the example the best profit is 11, against 14 without the rule.

Why is the dictionary for target sum bounded?

Every key is a signed sum of some of the numbers, so it lies between minus the total and plus the total. Here that is at most 25 keys; the largest dictionary actually reached has 13.

References

Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14, the elements of dynamic programming.
Skiena, S., The Algorithm Design Manual, chapter 10 on dynamic programming.
Kleinberg and Tardos, Algorithm Design, chapter 6.
Sedgewick and Wayne, Algorithms, section 5.4 (regular expressions), whose NFA simulation carries a set of states forward one input symbol at a time, and section 4.4 (acyclic shortest paths) for the day-by-state DAG.
Viterbi, A. J., "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm", IEEE Transactions on Information Theory 13, 1967, the state-machine DP over time.
The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.