---
title: "股票買賣家族模板"
url: "https://laigary.com/interview/coding/stock-template"
type: "note"
section: "coding"
date: "2026-07-26"
updated: "2026-07-26"
tags: ["Dynamic Programming", "Classic"]
---

# 股票買賣家族模板

LeetCode 的「Best Time to Buy and Sell Stock」有六題，題目敘述看起來各不相同，但**它們是同一個狀態機的六組參數**。與其把六題各背一次，不如把這個狀態機記住，再看每一題改了哪個旋鈕。

## 統一的狀態

任何一天結束時，我的狀態只有兩種：**手上有股票**，或**手上沒有**。加上「已經用掉幾次交易」，狀態就完整了：

```text
dp[i][k][0] = 第 i 天結束時、還剩 k 次交易額度、手上沒股票，此時的最大獲利
dp[i][k][1] = 第 i 天結束時、還剩 k 次交易額度、手上有股票，此時的最大獲利
```

每一天在每個狀態下都只有兩個選擇 —— **什麼都不做**，或**動作**（有股票就賣、沒股票就買）：

$$
dp[i][k][0] = \max\bigl(dp[i-1][k][0],\; dp[i-1][k][1] + prices[i]\bigr)
$$

$$
dp[i][k][1] = \max\bigl(dp[i-1][k][1],\; dp[i-1][k-1][0] - prices[i]\bigr)
$$

第一式讀作「今天沒股票 = 昨天就沒有，或昨天有、今天賣掉」；第二式讀作「今天有股票 = 昨天就有，或昨天沒有、今天買進」。

**交易次數在哪裡扣？** 這是唯一需要約定的地方 —— 買進時扣（`k-1`）或賣出時扣都可以，只要整份程式碼一致。上面的寫法是**買進時扣**。

### 遞迴版就是這個式子的直譯

```python
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:

        @cache
        def dfs(i, hold, remaining):
            if remaining == 0:
                return 0
            if i == len(prices):
                return 0

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

            do_something = 0

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

            return max(do_nothing, do_something)

        return dfs(0, False, k)
```

**這一份涵蓋 `k` 的四題**：換成 1 是 [121](/interview/coding/121-best-time-to-buy-and-sell-stock)、換成 2 是 [123](/interview/coding/123-best-time-to-buy-and-sell-stock-iii)、換成無限大是 [122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii)，它本身就是 [188](/interview/coding/188-best-time-to-buy-and-sell-stock-iv) 的自頂向下寫法。

但它**套不進 [309 冷凍期](/interview/coding/309-best-time-to-buy-and-sell-stock-with-cool-down) 和 [714 手續費](/interview/coding/714-best-time-to-buy-and-sell-stock-with-transaction-fee)** —— 那兩題改的不是 `k`。把三個旋鈕都拉出來當參數，才是真正六題通用的版本：

```python
class Solution:
    def maxProfit(self, prices: List[int], k=float('inf'), fee=0, cooldown=0) -> int:
        n = len(prices)

        @cache
        def dfs(i, hold, remaining):
            if i >= n:
                return 0

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

            if hold:
                # 賣出：收錢、額度 -1、跳過 cooldown 天不能買
                do_something = prices[i] + dfs(i + 1 + cooldown, False, remaining - 1)
            elif remaining > 0:
                # 買進：付錢 + 手續費，額度不變（賣出時才扣）
                do_something = -prices[i] - fee + dfs(i + 1, True, remaining)
            else:
                do_something = float('-inf')      # 沒額度了，不能買

            return max(do_nothing, do_something)

        return dfs(0, False, k)
```

三個旋鈕各自的位置：

| 旋鈕 | 改哪一行 | 為什麼 |
|---|---|---|
| `k` | `remaining - 1`、`elif remaining > 0` | 額度用完就不能再買 |
| `fee` | 買進的 `- fee` | 每筆交易的成本，買進時一次付掉 |
| `cooldown` | 賣出的 `i + 1 + cooldown` | 賣完直接把索引往後跳，中間那幾天連看都不看 |

`k` 預設是 `float('inf')`，而 **`inf - 1` 仍然是 `inf`** —— 所以「無限次」不需要特別處理，額度永遠扣不完，`remaining > 0` 也永遠成立。這個小技巧讓同一份程式碼不用為兩種情況分岔。

六題的呼叫方式：

```python
Solution().maxProfit(prices, k=1)            # 121
Solution().maxProfit(prices)                 # 122（k 預設無限）
Solution().maxProfit(prices, k=2)            # 123
Solution().maxProfit(prices, k=k)            # 188
Solution().maxProfit(prices, cooldown=1)     # 309
Solution().maxProfit(prices, fee=fee)        # 714
```

它甚至能算題目沒出過的組合，例如「最多兩次交易且每筆收手續費 2」`maxProfit(prices, k=2, fee=2)` —— 這是把家族當成一個狀態機來理解的好處：**新的變形不需要新的想法，只要多一個參數。**

面試時當然不會寫成這樣（沒有人要你解六題），但**心裡有這份通解，任何一題都不會卡住**：先寫出對應的簡化版，被追問變形時就知道要動哪一行。

### 那兩個分支哪個是買、哪個是賣

這段最容易看錯，因為**順序和直覺相反**：

| 分支 | 目前狀態 | 唯一能做的動作 | 金流 | 之後 |
|---|---|---|---|---|
| `if hold:` | **有**股票 | **賣出** | `+prices[i]`（收錢） | `hold → False`，`remaining - 1` |
| `else:` | **沒有**股票 | **買進** | `-prices[i]`（付錢） | `hold → True`，`remaining` 不變 |

所以**第一個分支是賣、第二個分支是買**。

會看錯是因為 `if hold:` 讀起來像「如果持有（就繼續持有）」，但它的意思是「**因為我持有，所以我這一步能做的事只有賣掉**」。`hold` 描述的是**現在的狀態**，分支裡寫的是**那個狀態下唯一可做的動作** —— 想成一個開關：有股票只能賣、沒股票只能買，不會有第三種選擇。

`do_nothing` 和 `do_something` 的命名也是這個意思：每一天在每個狀態下就是「動」或「不動」兩條路，取較好的那條。

**回傳值的語意是「從第 `i` 天起、在這個狀態下，往後還能賺多少」**。所以 `+prices[i]` / `-prices[i]` 是**這一步當下的現金流**，後面的 `dfs(...)` 是往後所有天的最佳結果，兩者相加才是「現在動作」這條路的總價值。

用 `prices = [3, 1, 5]`、`k = 1` 實際跑一遍（答案是 4，第 1 天買 1、第 2 天賣 5）：

| 第 `i` 天 | `hold` | 動作 | 金流 | 該分支回傳 |
|---|---|---|---|---|
| 0 | False | 買進 | `-3` | 2 |
| 1 | False | 買進 | `-1` | **4** |
| 1 | True | 賣出 | `+1` | 1 |
| 2 | False | 買進 | `-5` | -5 |
| 2 | True | 賣出 | `+5` | 5 |

第 1 天那兩列最能說明回傳值的語意：`hold=False` 時買進付了 1 塊卻回傳 4（因為後面能賣 5），`hold=True` 時賣出收了 1 塊卻只回傳 1（交易額度用完，後面是 0）。

### 交易次數在哪裡扣

這裡的 `remaining` 是在**賣出時**遞減（`dfs(i + 1, False, remaining - 1)`），也就是「一次完整交易 = 買 + 賣」，賣掉的當下才算用掉一次額度。和上面公式的約定（買進時扣）相反 —— **兩種都對，但整份程式碼只能扣一次，不能買也扣、賣也扣。**

## 六題各改了什麼

| 題目 | 交易次數 `k` | 額外規則 | 精簡解的形狀 |
|---|---|---|---|
| [121. Stock I](/interview/coding/121-best-time-to-buy-and-sell-stock) | **1** | — | 記錄歷史最低價，一個變數 |
| [122. Stock II](/interview/coding/122-best-time-to-buy-and-sell-stock-ii) | **無限** | — | `k` 消失，只剩 buy / sell 兩個變數 |
| [123. Stock III](/interview/coding/123-best-time-to-buy-and-sell-stock-iii) | **2** | — | 把兩次交易展開成四個變數 |
| [188. Stock IV](/interview/coding/188-best-time-to-buy-and-sell-stock-iv) | **任意 k** | — | 兩個長度 `k` 的陣列 |
| [309. with Cooldown](/interview/coding/309-best-time-to-buy-and-sell-stock-with-cool-down) | 無限 | 賣出後**隔一天**才能買 | 買進要看 `sells[i-2]` |
| [714. with Fee](/interview/coding/714-best-time-to-buy-and-sell-stock-with-transaction-fee) | 無限 | 每筆交易扣 `fee` | 買進時多減一個 `fee` |

**`k` 無限時 `k` 這個維度直接消失** —— 因為「還剩無限次」和「還剩無限次減一」是同一件事，狀態不需要記它。這是為什麼 122 / 309 / 714 的程式碼比 123 / 188 短。

## 滾動變數的寫法

有了狀態機，每一題的精簡解都是同一個模式：**用 `buys` 和 `sells` 兩個變數（或陣列）取代整張 dp 表**，因為轉移只依賴前一天。

```python
        buys = float('-inf')      # 手上有股票時的最大獲利
        sells = 0                 # 手上沒股票時的最大獲利

        for price in prices:
            buys = max(buys, sells - price)      # 今天買進
            sells = max(sells, buys + price)     # 今天賣出
        return sells
```

`buys` 初始化成 `-inf` 而不是 0，是因為「第 0 天之前就持有股票」不是合法狀態，用 `-inf` 讓 `max` 自動淘汰它。這個哨兵手法見 [Python 面試技巧](/interview/coding/python-tips-for-interview)。

要加規則就在這兩行上動手腳：

- **手續費**（714）：`buys = max(buys, sells - price - fee)`
- **冷凍期**（309）：買進時不能用昨天的 `sells`，要用前天的 → 得多存一格
- **有限次數**（123 / 188）：`buys` / `sells` 各變成長度 `k` 的陣列，內層再跑一次迴圈

## 面試時的講法

1. 先說**狀態**：「每天結束時我只有兩種狀態，手上有股票或沒有」
2. 再說**轉移**：「每天只有兩個選擇，什麼都不做或動作」
3. 最後說**這題的特殊規則**改了哪一行

照這個順序想，六題都是同一套說明，遇到沒看過的變形也接得下去 —— 這比精簡解本身更值錢，因為精簡解（例如 123 那四個變數）單獨看很像魔術。

## 複雜度

**通解（狀態機）**
- 時間 $O(nk)$ — `n` 天 × `k` 次額度 × 2 種持有狀態，每個狀態常數時間
- 空間 $O(nk)$ 記憶化，或 $O(k)$ 滾動

**`k` 無限的三題**（122 / 309 / 714）
- 時間 $O(n)$ — `k` 這個維度消失了
- 空間 $O(1)$ — 滾動變數

**`k` 有限的三題**（121 / 123 / 188）
- 時間 $O(nk)$ — 121 的 `k=1`、123 的 `k=2` 都是常數，所以實際上是 $O(n)$
- 空間 $O(k)$ — 同理，121 / 123 是 $O(1)$

其中 `n` 是天數、`k` 是允許的交易次數。

**188 有一個重要的捷徑**：當 `k > n / 2` 時，交易次數形同無限（一次交易至少要兩天），可以直接切換到 122 的 $O(n)$ 解法，避免開一個沒必要的大陣列。這個判斷值得記住，因為題目會給很大的 `k` 來測試。