Pattern Guide
State Machine DP
"Model transitions between states. Stock problems are the canonical example."
State machine DP models problems where you're in one of several states and transition between them. The buy/sell stock series is the classic example: states are (holding, not holding), and you add constraints (cooldown, fee, k transactions). Once you see the state diagram, the DP transitions write themselves.
18 min readdp problems →
Problems you can solve with this pattern
6 problems · click any to start solving
Base: two states (hold / not hold)
// State: hold = currently holding stock, cash = not holding
// Transition:
// hold[i] = max(hold[i-1], cash[i-1] - prices[i]) // keep holding OR buy today
// cash[i] = max(cash[i-1], hold[i-1] + prices[i]) // keep not holding OR sell today
// Answer: cash[n-1] (never better to hold at end)
// With unlimited transactions (Best Time II):
var maxProfit = function(prices) {
let hold = -prices[0], cash = 0;
for (let i = 1; i < prices.length; i++) {
const prevHold = hold, prevCash = cash;
hold = Math.max(prevHold, prevCash - prices[i]); // buy today
cash = Math.max(prevCash, prevHold + prices[i]); // sell today
}
return cash;
};
// With cooldown (after selling, can't buy next day):
// States: hold, cooldown (day after sell), rest (can buy)
var maxProfitCooldown = function(prices) {
let hold = -prices[0], cooldown = 0, rest = 0;
for (let i = 1; i < prices.length; i++) {
const [h, c, r] = [hold, cooldown, rest];
hold = Math.max(h, r - prices[i]); // buy from "rest" state only
cooldown = h + prices[i]; // sell → next day is cooldown
rest = Math.max(r, c); // rest: was already resting or was in cooldown
}
return Math.max(cooldown, rest);
};
// With transaction fee:
var maxProfitFee = function(prices, fee) {
let hold = -prices[0], cash = 0;
for (let i = 1; i < prices.length; i++) {
const [h, c] = [hold, cash];
hold = Math.max(h, c - prices[i]);
cash = Math.max(c, h + prices[i] - fee); // pay fee on sell
}
return cash;
};State machine DP is DP where the "state" is not just a position or count, but a discrete status (held/not held, locked/unlocked, active/inactive). At each step, you transition between states based on the current input. The stock problems are the canonical series: each variant adds one more constraint (cooldown, fee, max transactions), and each new constraint adds one more state.
The Stock Problem State Machine
Base: two states (hold / not hold)
// State: hold = currently holding stock, cash = not holding
// Transition:
// hold[i] = max(hold[i-1], cash[i-1] - prices[i]) // keep holding OR buy today
// cash[i] = max(cash[i-1], hold[i-1] + prices[i]) // keep not holding OR sell today
// Answer: cash[n-1] (never better to hold at end)
// With unlimited transactions (Best Time II):
var maxProfit = function(prices) {
let hold = -prices[0], cash = 0;
for (let i = 1; i < prices.length; i++) {
const prevHold = hold, prevCash = cash;
hold = Math.max(prevHold, prevCash - prices[i]); // buy today
cash = Math.max(prevCash, prevHold + prices[i]); // sell today
}
return cash;
};
// With cooldown (after selling, can't buy next day):
// States: hold, cooldown (day after sell), rest (can buy)
var maxProfitCooldown = function(prices) {
let hold = -prices[0], cooldown = 0, rest = 0;
for (let i = 1; i < prices.length; i++) {
const [h, c, r] = [hold, cooldown, rest];
hold = Math.max(h, r - prices[i]); // buy from "rest" state only
cooldown = h + prices[i]; // sell → next day is cooldown
rest = Math.max(r, c); // rest: was already resting or was in cooldown
}
return Math.max(cooldown, rest);
};
// With transaction fee:
var maxProfitFee = function(prices, fee) {
let hold = -prices[0], cash = 0;
for (let i = 1; i < prices.length; i++) {
const [h, c] = [hold, cash];
hold = Math.max(h, c - prices[i]);
cash = Math.max(c, h + prices[i] - fee); // pay fee on sell
}
return cash;
};State Machine Pattern
How to derive the DP:
1. Draw all states (circles)
2. Draw all transitions (arrows with conditions)
3. For each state, write: new_state = max/min over all ways to arrive at this state
4. Initialize: what state are we in on day 0?
5. Answer: which state has the best final value?
For stocks: draw "hold" and "cash" circles. Arrows: cash→hold (buy), hold→cash (sell). Add constraints as extra states (cooldown, etc.).
1. Draw all states (circles)
2. Draw all transitions (arrows with conditions)
3. For each state, write: new_state = max/min over all ways to arrive at this state
4. Initialize: what state are we in on day 0?
5. Answer: which state has the best final value?
For stocks: draw "hold" and "cash" circles. Arrows: cash→hold (buy), hold→cash (sell). Add constraints as extra states (cooldown, etc.).
State Machine DP blueprint:
1. Define all discrete states (hold, sold, rest, locked, etc.)
2. For each state s_i, write: s_i = max over all (prev_state + action_cost)
3. Initialize day 0: what can you do on day 0?
4. Answer: best value across all terminal states
Stock problems summary:
- 1 transaction: track minSoFar and maxProfit
- Unlimited: collect all positive gaps (greedy) or hold/cash DP
- Cooldown: 3 states (hold, sold/cooldown, rest)
- Fee: 2 states, subtract fee on sell
- k transactions: k pairs of (hold[j], cash[j]) states
1. Define all discrete states (hold, sold, rest, locked, etc.)
2. For each state s_i, write: s_i = max over all (prev_state + action_cost)
3. Initialize day 0: what can you do on day 0?
4. Answer: best value across all terminal states
Stock problems summary:
- 1 transaction: track minSoFar and maxProfit
- Unlimited: collect all positive gaps (greedy) or hold/cash DP
- Cooldown: 3 states (hold, sold/cooldown, rest)
- Fee: 2 states, subtract fee on sell
- k transactions: k pairs of (hold[j], cash[j]) states