309. Best Time to Buy and Sell Stock with Cool down

──────────────────────────────────────────────────────────────────────

交易次數無限，但賣出之後要隔一天才能再買（冷凍期一天）。

思路

這一題改的旋鈕是「賣出後有一天冷凍期」，交易次數仍然無限。 完整的狀態機和其他五題的對照見股票買賣家族模板。

從 122 出發，那題的買進轉移是：

buys[i] = max(buys[i-1], sells[i-1] - prices[i])     # 昨天賣完、今天就買

冷凍期要禁止的正是 sells[i-1] —— 昨天才賣掉的話，今天不能買。所以只要把它換成前天的狀態：

buys[i] = max(buys[i-1], sells[i-2] - prices[i])     # 要前天就已經沒有股票

整題的差別就是這個 i-1 改成 i-2。 這是我覺得這一家族最漂亮的地方 —— 規則的改變會精準對應到轉移式裡的某一項，不需要重新設計狀態。

為什麼不用多一個「冷凍中」的狀態

很多寫法會開三個狀態（持有 / 冷凍 / 空手可買）。那樣也對，而且比較好推理。但這裡只用兩個狀態加上「往回看兩天」也能表達同一件事：因為冷凍期只有一天，「前天沒有股票」就等價於「今天不在冷凍中」。

三狀態的版本比較容易推廣（冷凍期變成 m 天時），兩狀態的版本比較短。面試時先講三狀態，再說「因為冷凍期只有一天，可以壓成看 sells[i-2]」，兩邊都涵蓋到。

解題方向

自頂向下

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        @cache
        def dfs(i, hold, remaining, cooldown):
            if remaining == 0:
                return 0;
            if i == len(prices):
                return 0
            
            if cooldown:
                return dfs(i + 1, False, remaining, False)

            do_nothing = dfs(i + 1, hold, remaining, False)

            do_something = 0

            if hold:
                do_something = prices[i] + dfs(i + 1, False, remaining, True)
            else:
                do_something = -prices[i] + dfs(i + 1, True, remaining, False)

            return max(do_nothing, do_something)

        return dfs(0, False, 1, False)

在通解的三個參數上多加一個 cooldown 旗標。賣出時把它設成 True，下一天就只能跳過。

remaining 在這題是多餘的（次數無限，它從頭到尾都是 1 而且不會被減）。留著不影響正確性，但它會讓 cache 的鍵多一個維度、也讓讀者以為次數有限制 —— 拿掉會更清楚。

自底向上

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        buys = [float('-inf')] * len(prices)
        sells = [0] * len(prices)

        for i in range(len(prices)):
            buys[i] = max(buys[i-1] if i > 0 else -prices[i], (sells[i-2] if i > 1 else 0) - prices[i])
            sells[i] = max(sells[i-1] if i > 0 else 0, (buys[i-1] + prices[i] if i > 0 else 0))
        return sells[-1]

sells[i-2] if i > 1 else 0 就是上面說的那一個改動 —— 買進時要看前天的空手狀態。

前幾天的邊界用行內 if 處理（i > 0、i > 1），寫得很緊湊但有點難讀。另一種常見做法是在陣列前面多墊兩格，把邊界吃掉：

        n = len(prices)
        buys = [float('-inf')] * (n + 2)
        sells = [0] * (n + 2)
        for i in range(n):
            buys[i+2] = max(buys[i+1], sells[i] - prices[i])
            sells[i+2] = max(sells[i+1], buys[i+1] + prices[i])
        return sells[-1]

索引偏移換來沒有特例判斷，兩種風格看個人偏好 —— 重點是不要混用。

注意這題的 sells[i] 用的是 buys[i-1]（昨天的），不是同一輪剛更新的 buys[i]。122 可以偷懶用同一輪的值（當天買賣獲利 0，無害），但這題不行 —— 當天買當天賣會產生一個不該存在的冷凍期，把後面的狀態算錯。

補充

整個家族的對照見股票買賣家族模板。這題和 122、714 是同一組（k 無限），三題的程式碼幾乎一樣，差別只有一行 —— 一起看最有效率。

貪心在這題不成立：122 那個「把所有上漲區段吃下來」的解法會拆出很多筆交易，每一筆都帶來冷凍期，反而虧。加了任何限制就必須回到狀態機。

複雜度

時間 $O (n)$ — 一趟迴圈，每天常數次計算
空間 $O (n)$ 用陣列；因為只回看兩天，可以用四個變數滾動到 $O (1)$

其中 n 是天數。自頂向下版是 $O (n)$ 時間、 $O (n)$ 空間（cache 加遞迴堆疊）。