LeetCode 309 · 2-D DP · concept: dynamic-programming
Problem
Maximize profit with unlimited transactions, but after selling you must cooldown one day before buying again.
The idea — a state machine
Each day you’re in one of three states: holding a share, just sold (in cooldown), or rest (free to buy). Track the best profit in each and transition day by day.
hold= max(stay holding, buy today fromrest) →max(hold, rest - price)sold= sell today →hold + pricerest= max(stay resting, come off cooldown fromsold) →max(rest, sold)
def maxProfit(prices):
hold, sold, rest = float("-inf"), 0, 0
for price in prices:
prev_sold = sold
sold = hold + price # sell what we held
hold = max(hold, rest - price) # keep holding, or buy from rest
rest = max(rest, prev_sold) # stay rested, or finish cooldown
return max(sold, rest) # end not holdingTime O(n), space O(1).
State-machine DP
The cooldown couples days (you can’t buy right after selling), so a single running value can’t capture it — you need a value per state, with transitions encoding the rules. Modeling the problem as a small automaton and tracking the best profit in each node is the whole technique.
Key insight
Constraints that create “modes” (holding / cooldown / free) → a state-machine DP with one value per state. When “what you can do next depends on what you just did,” enumerate the states and write their transitions — far cleaner than trying to force one dimension.
Related
- concept: dynamic-programming
- relative: Best Time to Buy and Sell Stock (single transaction)
- prev: Longest Common Subsequence · next: Coin Change II
Software engineering
Infrastructure & security
Computer science
Hardware & engineering