With Cooldown / Fee
Three states: hold (have stock), sold (just sold, in cooldown), rest (no stock, not in cooldown). Each day, transition: hold→hold or hold→sold, sold→rest, rest→rest or rest→hold. Track max profit per state.
How It Works
Stock problems with a cooldown or transaction fee are cleanest as an explicit state machine. With cooldown, each day you occupy one of three states: hold (own a share), sold (sold today, tomorrow is frozen), or rest (own nothing, free to buy). Transitions follow the rules — hold comes from holding yesterday or buying from rest; sold comes only from hold; rest comes from rest or from sold (cooldown expiring) — and each state stores the best profit achievable while in it.
Every day updates a constant number of states from the previous day's values, giving O(n) time and O(1) space. The fee variant needs just two states (hold and cash) with the fee subtracted at sale. The lesson generalizes: when actions have lingering side effects, encode the situation as states, not just an index.
Step-by-Step Visualization
Code
static int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int price : prices) {
int prevSold = sold;
sold = hold + price;
hold = Math.max(hold, rest - price);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}Tips & Gotchas
Practice Problems
- 1Best Time to Buy and Sell Stock with Cooldown
- 2Best Time to Buy and Sell Stock with Transaction Fee
- 3Best Time to Buy and Sell Stock II
About the Stock / State Machine Pattern
Model the problem as states (holding stock, not holding, in cooldown) with transitions between them. Each day, you transition between states based on your action (buy, sell, hold). Track the max profit in each state.
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
Common Dynamic Programming Interview Problems
- Climbing Stairs
- Coin Change
- Longest Common Subsequence
- 0/1 Knapsack
- Edit Distance
- House Robber
- Longest Increasing Subsequence
- Word Break
Frequently Asked Questions
How do I identify the right set of states?
Enumerate every situation that changes which actions are legal tomorrow: owning a share, being mid-cooldown, being free to buy. If two situations permit identical futures, merge them. Cooldown needs three states precisely because 'just sold' and 'idle' allow different next moves.
Why does the fee version need only two states?
A fee changes the profit of a sale but not which actions are legal afterward — you can buy again immediately. So 'hold' and 'not hold' fully describe the world, with the fee folded into the sell transition: cash = max(cash, hold + price - fee).
Should the fee be charged on buy or on sell?
Either works as long as it is charged exactly once per transaction; subtracting it at the sell keeps the buy transition simple. Charging it at both ends, or forgetting it entirely on the initial buy, are the usual off-by-one-fee bugs.