Pattern Guide
Stock Trading DP
"Buy/sell with cooldown, fees, k transactions. State machine DP on market states."
Stock trading problems use state machine DP: states track whether you currently hold stock, how many transactions remain, and cooldown periods. Key insight: define states (holding, not holding, cooldown) and transitions between them. Base cases: first day. For k transactions: dp[day][transactions_left][holding]. Optimization: when k >= n/2, unlimited transactions.
Problems you can solve with this pattern
4 problems · click any to start solving
// Best Time to Buy and Sell Stock with Cooldown
// States: hold (have stock), free (no stock, no cooldown), cool (just sold, cooldown)
function maxProfitWithCooldown(prices) {
let hold = -Infinity, free = 0, cool = 0;
for (const price of prices) {
const prevHold = hold, prevFree = free, prevCool = cool;
hold = Math.max(prevHold, prevFree - price); // buy from free state
cool = prevHold + price; // sell (enter cooldown)
free = Math.max(prevFree, prevCool); // wait in free or exit cooldown
}
return Math.max(free, cool);
}
// k transactions: dp[k][0] = max profit, k trans used, not holding
// dp[k][1] = max profit, k trans used, holding
function maxProfitKTransactions(k, prices) {
const n = prices.length;
if (k >= Math.floor(n / 2)) {
// Unlimited transactions
let profit = 0;
for (let i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i-1]);
return profit;
}
const dp = Array.from({length: k+1}, () => [-Infinity, -Infinity]);
dp[0][0] = 0;
for (const price of prices) {
for (let t = k; t >= 1; t--) {
dp[t][0] = Math.max(dp[t][0], dp[t][1] + price); // sell
dp[t][1] = Math.max(dp[t][1], dp[t-1][0] - price); // buy
}
}
return Math.max(0, ...dp.map(d => d[0]));
}Stock DP states: hold = max profit when holding a stock today; free = max profit when not holding and no cooldown; cool = max profit in cooldown (just sold). Transitions: hold = max(hold, free - price); cool = hold + price; free = max(free, cool). General k-transaction: dp[k][0/1] where 0=not holding, 1=holding. When k >= n/2, treat as unlimited.
// Best Time to Buy and Sell Stock with Cooldown
// States: hold (have stock), free (no stock, no cooldown), cool (just sold, cooldown)
function maxProfitWithCooldown(prices) {
let hold = -Infinity, free = 0, cool = 0;
for (const price of prices) {
const prevHold = hold, prevFree = free, prevCool = cool;
hold = Math.max(prevHold, prevFree - price); // buy from free state
cool = prevHold + price; // sell (enter cooldown)
free = Math.max(prevFree, prevCool); // wait in free or exit cooldown
}
return Math.max(free, cool);
}
// k transactions: dp[k][0] = max profit, k trans used, not holding
// dp[k][1] = max profit, k trans used, holding
function maxProfitKTransactions(k, prices) {
const n = prices.length;
if (k >= Math.floor(n / 2)) {
// Unlimited transactions
let profit = 0;
for (let i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i-1]);
return profit;
}
const dp = Array.from({length: k+1}, () => [-Infinity, -Infinity]);
dp[0][0] = 0;
for (const price of prices) {
for (let t = k; t >= 1; t--) {
dp[t][0] = Math.max(dp[t][0], dp[t][1] + price); // sell
dp[t][1] = Math.max(dp[t][1], dp[t-1][0] - price); // buy
}
}
return Math.max(0, ...dp.map(d => d[0]));
}- 1 transaction: track min price seen, max(0, price - min)
- Unlimited: greedy, sum all positive differences
- Cooldown: 3-state DP (hold, sold/cooldown, rest)
- Fee: 2-state DP (hold, free), subtract fee on sell
- k transactions: dp[k][holding], iterate k from k down to 1
Key insight: A "transaction" = one buy + one sell. When k ≥ n/2, any two consecutive days can form a transaction, so effectively unlimited.
State machine approach works for all variants: Just adjust the state transitions for the specific constraint (cooldown, fee, k limit).