LeetCode 309 · Medium · 2-D Dynamic Programming

Best Time to Buy and Sell Stock with Cooldown

Given a stock's price on each day, make as many buy-then-sell trades as you like, holding at most one share at a time. After a sale you must wait one day before buying again. Return the best total profit.

O(n)time
O(n)space
2 states per daybuying or selling

comma-separated prices · 1–8 days · 0 to 99 each

buyingbuy −p →sellingsell +p →cooldown→ buying
vs

dp row = state on that day · column header = price · cell = best profit from that day on · end = past the last day

Call stack bottom → top

private int[] prices;private Integer[][] dp; // dp[i][buying ? 1 : 0] -> max profitpublic int maxProfit(int[] prices) { this.prices = prices; dp = new Integer[prices.length][2]; return dfs(0, true);}private int dfs(int i, boolean buying) { if (i >= prices.length) { return 0; } int s = buying ? 1 : 0; if (dp[i][s] != null) { return dp[i][s]; } int cooldown = dfs(i + 1, buying); if (buying) { int buy = dfs(i + 1, false) - prices[i]; dp[i][s] = Math.max(buy, cooldown); } else { int sell = dfs(i + 2, true) + prices[i]; dp[i][s] = Math.max(sell, cooldown); } return dp[i][s];}
i, buying
—
prices[i]
—
cooldown
—
memo hits
0

Why it works

  1. Brute force tries every action on every day (buy, sell or wait, whichever is legal): up to 3n plans.
  2. A day has only two situations: you may buy (buying) or you hold a share and may sell. Either way you can also wait (cooldown in the code). Buying moves you to the selling state tomorrow; selling jumps to the buying state two days ahead, which is the forced cooldown.
  3. Complexity: n days × 2 states, each solved once from two cached answers: O(n) time and O(n) space for the memo and the recursion.
  4. Pitfall: a sale goes to dfs(i + 2, ...), not i + 1: that skipped day is the whole twist. Without it this is Best Time II (122), where every rising day is profit.
  5. O(1) space: run the same state machine forward with three numbers (holding, just sold, resting) and update them each day. Related: with a fee per trade (714), subtract it on each sale instead of skipping a day.