股票買賣家族模板

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

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

統一的狀態

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

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

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

d p [i] [k] [0] = \max (d p [i - 1] [k] [0], d p [i - 1] [k] [1] + p r i c e s [i])

d p [i] [k] [1] = \max (d p [i - 1] [k] [1], d p [i - 1] [k - 1] [0] - p r i c e s [i])

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

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

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

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、換成 2 是 123、換成無限大是 122，它本身就是 188 的自頂向下寫法。

但它套不進 309 冷凍期和 714 手續費 —— 那兩題改的不是 k。把三個旋鈕都拉出來當參數，才是真正六題通用的版本：

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 也永遠成立。這個小技巧讓同一份程式碼不用為兩種情況分岔。

六題的呼叫方式：

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	1	—	記錄歷史最低價，一個變數
122. Stock II	無限	—	`k` 消失，只剩 buy / sell 兩個變數
123. Stock III	2	—	把兩次交易展開成四個變數
188. Stock IV	任意 k	—	兩個長度 `k` 的陣列
309. with Cooldown	無限	賣出後隔一天才能買	買進要看 `sells[i-2]`
714. with Fee	無限	每筆交易扣 `fee`	買進時多減一個 `fee`

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

滾動變數的寫法

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

        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 面試技巧。

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

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

面試時的講法

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

照這個順序講，六題都是同一套說明，而且面試官問到別的變形時可以直接接下去 —— 這比精簡解本身更值錢，因為精簡解（例如 123 那四個變數）單獨看很像魔術，講不出來歷會顯得是背的。

複雜度

通解（狀態機）

時間 $O (n k)$ — n 天 × k 次額度 × 2 種持有狀態，每個狀態常數時間
空間 $O (n k)$ 記憶化，或 $O (k)$ 滾動

k 無限的三題（122 / 309 / 714）

時間 $O (n)$ — k 這個維度消失了
空間 $O (1)$ — 滾動變數

k 有限的三題（121 / 123 / 188）

時間 $O (n k)$ — 121 的 k=1、123 的 k=2 都是常數，所以實際上是 $O (n)$
空間 $O (k)$ — 同理，121 / 123 是 $O (1)$

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

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