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

# 188. Best Time to Buy and Sell Stock IV

[188\. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv)

最多可以完成 **`k` 筆**交易，求最大獲利。

## 思路

**這一題就是整個家族的通解 —— `k` 是參數。** 完整的狀態機推導見 [股票買賣家族模板](/interview/coding/stock-template)。

其他五題都是這題的特例：`k=1` 是 [121](/interview/coding/121-best-time-to-buy-and-sell-stock)、`k=2` 是 [123](/interview/coding/123-best-time-to-buy-and-sell-stock-iii)、`k=∞` 是 [122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii)。所以**面試時如果一時想不起某一題的精簡解，寫這題的程式碼一定不會錯**。

狀態是三個維度：**第幾天、還剩幾次交易、手上有沒有股票**。每天在每個狀態下只有兩個選擇：什麼都不做，或動作（有就賣、沒有就買）。

### 一個必要的捷徑

`k` 可能給得很大（題目會拿這個測你）。但**一次完整交易至少要兩天**（一天買、一天賣），所以 `n` 天最多只能做 `n // 2` 筆交易。

當 `k > n // 2` 時，次數限制形同不存在 —— 直接切換成 [122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii) 的無限次解法就好，$O(n)$ 而且不用開一個 `k` 那麼大的陣列。少了這個判斷，`k = 10^9` 的測資會直接記憶體爆掉。

## 解題方向

### 自頂向下

```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)
```

三個參數就是三個維度，`@cache` 負責記憶化。**這一份是整個家族最好記的寫法** —— 它和狀態機的文字描述一行一行對得起來，不需要記任何精簡技巧。

`remaining` 在**賣出時**遞減，也就是「買 + 賣 = 一次交易」。買進時扣也可以，只要自己一致。

缺點是遞迴深度是 `n`，而且沒有上面那個 `k > n // 2` 的捷徑，`k` 很大時 cache 會很大。

### 自底向上

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

        if k > len(prices)//2:
            max_profit = 0
            for i in range(1, len(prices)):
                max_profit += max(0, prices[i] - prices[i-1])
            return max_profit

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

        for price in prices:
            for i in range(k):
                if i == 0:
                    buys[i] = max(buys[i], 0 - price)
                else:
                    buys[i] = max(buys[i], sells[i-1] - price)
                sells[i] = max(sells[i], buys[i] + price)
        return sells[-1]
```

把 [123](/interview/coding/123-best-time-to-buy-and-sell-stock-iii) 的四個變數換成兩個長度 `k` 的陣列，內層迴圈跑過每一次交易額度。`buys[i]` / `sells[i]` 就是「第 `i+1` 次交易買進 / 賣出後的最大獲利」。

**`sells[i-1] - price` 是整題的核心**，意思是「第 `i+1` 次買進的錢，來自第 `i` 次交易賺完之後的餘額」—— 和 123 那條流水線是同一件事，只是變成了迴圈。

`if k > len(prices)//2` 那段就是上面說的捷徑。

## 補充

**整個家族的對照**見 [股票買賣家族模板](/interview/coding/stock-template)。

**面試策略**：先寫自頂向下（好解釋、不會錯），講清楚三個狀態維度，再說「如果 `k` 很大我會加一個判斷切到無限次的解法」。要求優化空間時再改寫成自底向上的滾動陣列。

## 複雜度

**自頂向下**
- 時間 $O(nk)$ — 狀態數是 `n × k × 2`，每個常數時間
- 空間 $O(nk)$ — cache 加上 $O(n)$ 遞迴堆疊

**自底向上**
- 時間 $O(nk)$ — 外層 `n` 天、內層 `k` 次額度；`k > n/2` 時走捷徑變成 $O(n)$
- 空間 $O(k)$ — 兩個長度 `k` 的陣列

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

加了那個捷徑之後，實際的時間上限是 $O(n \cdot \min(k, n/2))$，最壞是 $O(n^2)$ —— 但因為 `k` 超過 `n/2` 就會走另一條路，不會真的退化。