Best Time to Buy and Sell Stock IV
dp[t][d] = max(carry yesterday, sell today against the best transaction-(t-1) buy price so far)
Add a second dimension to the single-transaction DP: dp[t][d] is the best profit using at most t transactions through day d. Each day you either carry yesterday's value forward, or sell today against the cheapest effective buy price the (t-1)-transaction row has offered so far. Tracking that running best price as diff = max(dp[t-1][m] - prices[m]) turns an O(k*n^2) table into O(k*n), because diff only ever needs updating once per day, not re-scanned.
Details
Animated on: k = 2, prices = [3, 2, 6, 5, 0, 3] — with at most 2 buy-sell transactions, find the maximum achievable profit.
Problem:Best Time to Buy and Sell Stock IVHard
dp[t][d] = max(carry yesterday, sell today against the best transaction-(t-1) buy price so far)
step 1 / 14
dp[t][d] = max profit using at most t transactions through day d
dp[0][d] = 0 for every day: with zero transactions allowed, no profit is possible no matter which prices you see.
1FUNCTION maxProfitK(k, prices):2 n <- LENGTH(prices)3 dp <- (k+1) x n TABLE OF 04 FOR t FROM 1 TO k:5 diff <- dp[t-1][0] - prices[0]6 FOR d FROM 1 TO n-1:7 dp[t][d] <- MAX(dp[t][d-1], prices[d] + diff)8 diff <- MAX(diff, dp[t-1][d] - prices[d])9 RETURN dp[k][n-1]
← / → step · space play · Home restart
Every step in words
Show all 14 steps
- dp[0][d] = 0 for every day: with zero transactions allowed, no profit is possible no matter which prices you see.
- Row t=1 begins: dp[1][0] = 0 (nothing has happened before day 0). The best "buy price" available so far for this transaction is prices[0] = 3, so diff starts at 0 - 3 = -3.
- Selling on day 1 would only make -1 (prices[1] + diff = 2 + -3), worse than just carrying yesterday's dp[1][0] = 0, so dp[1][1] stays 0.
- Selling on day 2 at 6 beats carrying yesterday's dp[1][1] = 0: prices[2] + diff = 6 + -2 = 4, buying back against the profit banked by day 1's dp[0][1]. dp[1][2] = 4.
- Selling on day 3 would only make 3 (prices[3] + diff = 5 + -2), worse than just carrying yesterday's dp[1][2] = 4, so dp[1][3] stays 4.
- Selling on day 4 would only make -2 (prices[4] + diff = 0 + -2), worse than just carrying yesterday's dp[1][3] = 4, so dp[1][4] stays 4.
- Selling on day 5 would only make 3 (prices[5] + diff = 3 + 0), worse than just carrying yesterday's dp[1][4] = 4, so dp[1][5] stays 4.
- Row t=2 begins: dp[2][0] = 0 (nothing has happened before day 0). The best "buy price" available so far for this transaction is prices[0] = 3, so diff starts at 0 - 3 = -3.
- Selling on day 1 would only make -1 (prices[1] + diff = 2 + -3), worse than just carrying yesterday's dp[2][0] = 0, so dp[2][1] stays 0.
- Selling on day 2 at 6 beats carrying yesterday's dp[2][1] = 0: prices[2] + diff = 6 + -2 = 4, buying back against the profit banked by day 1's dp[1][1]. dp[2][2] = 4.
- Selling on day 3 would only make 3 (prices[3] + diff = 5 + -2), worse than just carrying yesterday's dp[2][2] = 4, so dp[2][3] stays 4.
- Selling on day 4 would only make -1 (prices[4] + diff = 0 + -1), worse than just carrying yesterday's dp[2][3] = 4, so dp[2][4] stays 4.
- Selling on day 5 at 3 beats carrying yesterday's dp[2][4] = 4: prices[5] + diff = 3 + 4 = 7, buying back against the profit banked by day 4's dp[1][4]. dp[2][5] = 7.
- dp[2][5] = 7 — the best achievable profit using at most 2 transactions across all 6 days.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.