Lesson 32.1 · Advanced DP
State Machine DP
When each day you can be in one of a few modes (holding stock, just sold, resting), keep the best value for each mode and update them together from the previous day.
14 min
Think of it like this
A traffic light that can only move green → yellow → red → green. If you know the best score for each colour yesterday, today's best for each colour comes from the colours that can lead into it.
1.Draw the states, then write the transitions
Stock with cooldown has three states: hold (own a share), sold (sold today, must cool down tomorrow), rest (no share, free to buy). Transitions: rest → hold (buy, −price), hold → hold, hold → sold (sell, +price), sold → rest, rest → rest.
Each day: hold' = max(hold, rest − p), sold' = hold + p, rest' = max(rest, sold), all computed from yesterday's values. The answer is max(sold, rest) at the end.
Variants change the machine: a fee subtracts on sell; at most k transactions adds a counter (k pairs of buy/sell states); unlimited transactions collapses to two states.
prices = [1, 2, 3, 0, 2]day 0, p = 1(vars)
Step 1/5Day 0: buying gives hold = −1.
Remember
- List states and allowed moves first.
- Update all states from yesterday's values.
- Unreachable start states = −∞.
Common mistakes
- Using today's updated value in another state's update by accident (save old values first).
Words used in this lesson
- State machine
- A fixed set of modes with rules for moving between them.