DPAlgorithmaka finite-state DP, status DP, stock DP

State Machine DP

State is (position, small status flag); transitions are the edges of a tiny automaton evaluated once per input element.

▶ VisualizePattern: Dynamic ProgrammingPractice (2)
Progress

Overview

Many linear problems are not solvable with a single dp[i] because the best decision at i depends on a mode you are in: holding a stock or not, in cooldown or not, last character was a vowel or not, currently inside a segment or not. The fix is to add a small categorical dimension: dp[i][s] for status s in a set of k values, with transitions given by the allowed moves between statuses. The result is a finite automaton whose edges are re-evaluated for each input element.

The classic family is "best time to buy and sell stock" with cooldown, transaction fee, or at most k transactions: states hold / free / cooldown, transitions buy, sell, rest. Other members: paint house (status = colour of last house), delete-and-earn, counting strings with forbidden adjacent patterns, and House Robber written as robbed / skipped.

Time is O(n · k · k) in general (k statuses, each looking at k predecessors), and O(n · k) when the automaton is sparse. Space is O(k) since only the previous position is read. Constraints are typically n ≤ 10^5 with k ≤ 3–10, or n ≤ 1000 with k up to a few hundred (colours, transaction counts).

automatonstock problemsflagsO(n·k)cooldown

Intuition

A mental model before the formal terms.

Draw the statuses as circles and the allowed moves as arrows: free --buy--> hold, hold --sell--> cooldown, cooldown --rest--> free, plus self-loops for doing nothing. Now feed prices in one at a time; each circle keeps the best profit you could have while sitting in it. After each price, every circle updates from its incoming arrows. The answer is the best circle you can end in with no stock in hand.

The point is that "what you can do next" is entirely determined by which circle you stand in, so the circle is the whole memory you need.

How it works

  1. State: dp[i][s] = best value after processing element i and being in status s. Enumerate the statuses explicitly and draw the transition graph before coding.
  2. Transition: for each status t and each edge s → t with the cost/gain of taking it at element i: dp[i][t] = best over incoming s of dp[i-1][s] + gain(s → t, a[i]).
  3. Base cases: dp[0][start] = 0 and all unreachable statuses = -INF (or +INF for minimization). Getting the initial "impossible" values right is the main source of bugs.
  4. Order: increasing i; compute all statuses of step i from step i-1 (use temporaries so updates within a step do not feed each other). Optimization: keep k variables instead of a table.

Why it works

The status captures every constraint that the past imposes on the future (e.g. "you cannot buy while holding"). Given the status, the optimal continuation is independent of how you reached it, which is exactly optimal substructure.

Because each step reads only the previous step, increasing i is a valid order, and the per-step work is bounded by the number of automaton edges.

Recognition

How to tell a problem wants this.

  • Rules of the form "you cannot do X immediately after Y" (cooldown, no two adjacent, must alternate).
  • A small number of modes/phases the process can be in, each with different allowed actions.
  • Stock, painting, tiling, or string-generation problems with constraints on consecutive choices.
  • A plain dp[i] solution "almost works" but needs to know one extra bit about the previous step.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related House Robber visualization.

2
0
7
1
9
2
3
3
1
4
8
5
4
6
0123456
27·····
1/12Base cases: with one house rob it (2); with two houses rob the richer one (7) because adjacent houses cannot both be robbed.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn House Robber →
1dp[0] = v[0]; dp[1] = max(v[0], v[1])
2for i in 2 .. n-1:
3  take = dp[i-2] + v[i]
4  skip = dp[i-1]
5  dp[i] = max(take, skip)
6return dp[n-1]
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1# stock with cooldown: statuses hold, free (can buy), cool (just sold)
2hold = -INF, free = 0, cool = -INF
3for p in prices:
4  new_hold = max(hold, free - p)   # keep holding, or buy today
5  new_free = max(free, cool)       # stay free, or cooldown ended
6  new_cool = hold + p              # sell today
7  hold, free, cool = new_hold, new_free, new_cool
8return max(free, cool)

Implementations

1# Representative problem: best time to buy and sell stock with cooldown
2def max_profit(prices: list[int]) -> int:
31 · States: hold, just sold (cooldown), resting
4    NEG = float("-inf")
5    hold, sold, rest = NEG, NEG, 0    # holding / sold today / free to buy
62 · Daily transitions
7    for p in prices:
83 · Each new state reads only yesterday's values
9        hold, sold, rest = (
10            max(hold, rest - p),      # keep holding, or buy after resting
11            hold + p,                 # sell today -> cooldown tomorrow
12            max(rest, sold),          # idle; cooldown ends here
13        )
144 · Answer: end without holding stock
15    return int(max(sold, rest))
16 
17 
18if __name__ == "__main__":
19    print(max_profit([1, 2, 3, 0, 2]))  # 3 (buy, sell, cooldown, buy, sell)
Walkthrough
  1. Representative example of state-machine DP: three statuses (hold / sold / rest); day i depends only on day i - 1, so three variables suffice.
  2. The tuple assignment evaluates the entire right-hand side before rebinding — Python's built-in simultaneous update, no temporaries needed.
  3. float("-inf") marks unreachable states; max ignores it and -inf + p stays -inf.
  4. Buying is only reachable from rest (rest - p); the missing sold -> hold edge is the cooldown rule.
  5. int(max(sold, rest)) converts the float sentinel type back to int for the caller.
Complexity (this implementation)
time O(n) · space O(1)
Language notes
  • Tuple assignment is the idiomatic simultaneous update and eliminates the classic ordering bug entirely.
  • float("-inf") mixes fine with ints in comparisons and arithmetic; convert the final answer back with int().
  • This is a bottom-up loop, so no recursion limit concerns; a memoized @lru_cache version over (day, status) also works but is slower.
Common mistakes in this language
  • Splitting the tuple assignment into three ordinary statements and reading already-updated values.
  • Starting rest at -inf instead of 0.
  • Including hold in the final max.
Language differences that matter here
  • Unreachable sentinel: JS/TS -Infinity and Python float("-inf") absorb additions safely; C++ needs a finite very-negative long long kept away from LLONG_MIN to avoid overflow UB.
  • Simultaneous state update: Python tuple assignment is atomic by construction; C++/JS/TS need explicit next* temporaries (or JS/TS array destructuring, which allocates).
  • Python's -inf is a float, so the final answer should be converted back to int; the other languages stay in one numeric type throughout.

Complexity

Best
—
Average
—
Worst
O(n · k²) for k statuses (O(n · k) when the automaton is sparse)
Space
O(k)

k is usually 2–4, so this is effectively linear.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sequential decisions with a small set of modes that restrict the next action.
  • Stock problems with cooldown/fee/limited transactions; painting/tiling with adjacency rules.
  • Whenever adding one small status flag turns a broken dp[i] into a correct one.
Avoid it when
  • The "status" would need to be unbounded (the full history) — it is no longer a finite automaton; reconsider the state.
  • No constraint links consecutive decisions — plain 1D (Linear) DP or a greedy suffices (stock II with unlimited transactions is greedy).
  • The status space is huge (hundreds of thousands) — think of it as a graph problem or use a different formulation.

Alternatives

1D (Linear) DPGreedy Algorithms2D (Two-Sequence) DP

Common mistakes

  • Initializing unreachable statuses to 0 instead of -INF, which lets "sell without ever buying" produce profit.
  • Updating statuses in place so a later status reads the already-updated value of an earlier one from the same day.
  • Forgetting which statuses are valid at the end (must not be holding).
  • Not drawing the automaton first and missing a transition (e.g. free → free self-loop).

Interview patterns

  • Best Time to Buy and Sell Stock II/III/IV, with Cooldown, with Transaction Fee.
  • Paint House / Paint Fence (status = last colour).
  • House Robber as a two-status machine; Delete and Earn.
  • Count strings/arrays satisfying local adjacency rules (vowel permutations, no consecutive 1s).
Interview questions on this
Mock interviews

Example problems

Task SchedulermediumHouse Robbermedium