States and transitions
Some problems are clearest when phrased as a small automaton: a few named states with allowed moves between them. DP then tracks the best value in each state at each step. Stock trading with cooldowns and constraints on consecutive actions fit this view.
A trading example
Consider buying and selling stock with a cooldown. The states might be:
- Holding a share.
- Sold today and now resting in cooldown.
- Free to buy and not holding.
Each day, transitions update these from the previous day. Holding comes from staying held or buying while free. The free state comes from staying free or finishing a cooldown. The answer is the best non holding state on the last day.
Why this helps
Naming states keeps the recurrence honest: every legal move is an explicit transition, so impossible sequences cannot sneak in. The work is the number of states times the number of steps.
Key idea
State machine DP names a few legal states and their transitions, then carries the best value of each state forward step by step, which cleanly enforces rules about order and cooldowns.