188. Best Time to Buy and Sell Stock IV

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

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

思路

這一題就是整個家族的通解 —— k 是參數。 完整的狀態機推導見股票買賣家族模板。

其他五題都是這題的特例：k=1 是 121、k=2 是 123、k=∞ 是 122。所以面試時如果一時想不起某一題的精簡解，寫這題的程式碼一定不會錯。

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

一個必要的捷徑

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

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

解題方向

自頂向下

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 會很大。

自底向上

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 的四個變數換成兩個長度 k 的陣列，內層迴圈跑過每一次交易額度。buys[i] / sells[i] 就是「第 i+1 次交易買進 / 賣出後的最大獲利」。

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

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

補充

整個家族的對照見股票買賣家族模板。

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

複雜度

自頂向下

時間 $O (n k)$ — 狀態數是 n × k × 2，每個常數時間
空間 $O (n k)$ — cache 加上 $O (n)$ 遞迴堆疊

自底向上

時間 $O (n k)$ — 外層 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 就會走另一條路，不會真的退化。