---
title: "309. Best Time to Buy and Sell Stock with Cool down"
url: "https://laigary.com/interview/coding/309-best-time-to-buy-and-sell-stock-with-cool-down"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Dynamic Programming", "Classic"]
---

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

[309\. Best Time to Buy and Sell Stock with Cool down](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)

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

## 思路

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

從 [122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii) 出發，那題的買進轉移是：

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

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

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

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

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

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

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

## 解題方向

### 自頂向下

```python
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 的鍵多一個維度、也讓讀者以為次數有限制 —— 拿掉會更清楚。

### 自底向上

```python
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`），寫得很緊湊但有點難讀。另一種常見做法是**在陣列前面多墊兩格**，把邊界吃掉：

```python
        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](/interview/coding/122-best-time-to-buy-and-sell-stock-ii) 可以偷懶用同一輪的值（當天買賣獲利 0，無害），**但這題不行** —— 當天買當天賣會產生一個不該存在的冷凍期，把後面的狀態算錯。

## 補充

**整個家族的對照**見 [股票買賣家族模板](/interview/coding/stock-template)。這題和 [122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii)、[714](/interview/coding/714-best-time-to-buy-and-sell-stock-with-transaction-fee) 是同一組（`k` 無限），三題的程式碼幾乎一樣，差別只有一行 —— 一起看最有效率。

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

## 複雜度

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

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