309. Best Time to Buy and Sell Stock with Cooldown

T: O(n)

S: O(1)

```java
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int hasStock = -prices[0]; // has stock
        int sold = 0; // sold
        int cooled = 0; // cooled
        for (int i = 1; i < n; i++) {
            int hasStock2 = hasStock;
            int sold2 = sold;
            int cooled2 = cooled;
            // buy sell cooldown buy sell, so hasstock(buy), can be from cooldown or it already has stock
            hasStock = Math.max(hasStock2,  cooled2 - prices[i]); 
            
            // from has stock and money
            sold = hasStock2 + prices[i];
            // from cooldown, or sold
            cooled = Math.max(cooled2, sold2);
        }
        return Math.max(sold, cooled);
    }
}
/**

T: O(n)
S: O(n)

buy sell cooldown buy sell

has stock - 0
sold - 1
cooled - 2

has stock: Math.max(dp[i][0] = dp[i-1][0],  dp[i-1][2] - price[i]) -> max(has stock, cooled - price[i])
sold:      dp[i][1] = dp[i-1][0] + price[i]
cooled   : dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]) -> max(cooled, sold)

return Math.max(sold, cooled);  (has stock must not the best result, it has stock)
 */
```

```java
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0]; // has stock
        dp[0][1] = 0; // sold
        dp[0][2] = 0; // cooled
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],  dp[i-1][2] - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]);
        }
        return Math.max(dp[n-1][1], dp[n-1][2]);
    }
}
```

1. what part I stuck?

on dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);  //buy
I think about the situation of dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // sell
because sell in i-1 day, can I buy use i - 2 day?
Totally ok! becasue the most optimized case are all dependent, remember?
so I can define i-2 for buying!

2. After seeing solution, think about how this person came out this solution? what’s their thought process, why we have the same question and same knowledge, but I cant?

3. note strategy! remember it!

time: O(n)

space: O(n)

這題沒有限制交易次數, 所以跟 II 類似, 但有冷卻期的限制

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

因此，如果要在第i天買入股票，第二個狀態轉移方程中就不能使用T[i - 1][k][0]，而應該使用T[i - 2][k][0]

class Solution {
    public int maxProfit(int[] prices) {
        // on the next day (i.e., cooldown one day).
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);  // sell
        // dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);  //buy

        if (prices == null || prices.length < 2) return 0;
        int n = prices.length;
        
        int dp[][] = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);  // sell
            dp[i][1] = Math.max(dp[i-1][1], (i >= 2 ? dp[i-2][0] : 0) - prices[i]);  //buy
        }
        return dp[n-1][0];
    }
}

use variables

time: O(n)

space: O(1)

class Solution {
    public int maxProfit(int[] prices) {
        // on the next day (i.e., cooldown one day).
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);  // sell
        // dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);  //buy

        if (prices == null || prices.length < 2) return 0;
        int n = prices.length;
        
        int dp0 = 0;
        int dp1 = -prices[0];
        int prevDp0 = 0;
        
        for (int i = 1; i < n; i++) {
            int newDp0 = Math.max(dp0, dp1 + prices[i]);  // sell
            int newDp1 = Math.max(dp1, prevDp0 - prices[i]);  //buy
            prevDp0 = dp0;
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
}