309. Best Time to Buy and Sell Stock with Cooldown - Medium

前往題目

思路

一如其他dp題目，轉換公式是最重要的

1. 有三種狀況
   1. 持有
   2. 賣出
   3. 冷卻
2. 如果當前選擇持有，那昨天只會有兩種可能
   1. 持有
   2. 冷卻，然後今天選擇持有所以要扣掉今天的價格
3. 如果當前選擇賣出，那只有一種可能，昨天是持有的，而今天賣出，所以加上今天的賣出價
4. 如果當前選擇冷卻，昨天就有兩種可能
   1. 同樣是冷卻(不可能持有，因為要賣出才會冷卻，所以昨天冷卻今天一樣可以選擇冷卻，即等待的意思)
   2. 賣出

有了這些想法，code就再簡單不過了

要注意的是初始值，hold初始值應設為<= -prices[i]，因為第一天要不選擇買入，要不選擇等待，如果初始設為0，那第一天賣出就會選到0，因為賣出後錢變成負數

Code

NeetCode大大也有解析，但官神的解法更加簡潔明瞭，而且只需要O(1)空間

class Solution {
    public int maxProfit(int[] prices) {
        // For first round, if buy, then -prices[0]
        int hold = -prices[0];
        int sold = 0, cooled = 0;

        // Go through everyday
        for (int i = 0; i < prices.length; ++i) {
            // Store previous values
            int holdTemp = hold, soldTemp = sold, cooledTemp = cooled;

            // Either hold previously or finished cooling
            hold = Math.max(holdTemp, cooled-prices[i]);
            // Only hold yesterday before sold
            sold = holdTemp + prices[i];
            // Either wait for perfect timing to buy or just sold yesterday
            cooled = Math.max(cooledTemp, soldTemp);
        }

        // Don't wanna hold cuz it costs money
        return Math.max(sold, cooled);
    }
}