State Machine Dynamic Programming: Modeling Complex Action Transitions & Cooldowns

When a decision process involves mutually exclusive modes (e.g. holding a stock, resting in cooldown, or waiting to buy), representing the problem as a Finite State Machine (FSM) clarifies transitions and prevents edge-case errors.

1. State Machine Representation (LeetCode 309)

Consider stock trading with a 1-day cooldown after selling. We define three states for day $i$:

• hold[i]: Maximum profit holding a share.
• sold[i]: Maximum profit having sold a share on day $i$.
• rest[i]: Maximum profit in cooldown or resting state.

hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]);
sold[i] = hold[i - 1] + prices[i];
rest[i] = max(rest[i - 1], sold[i - 1]);