MediumRating 1708
309. Best Time to Buy and Sell Stock with Cooldown
arraydynamic-programming
解題說明
Best Time to Buy and Sell Stock with Cooldown（309）
題目描述：給定每日股票價格陣列 prices，可以多次買賣，但賣出後必須休息一天（冷靜期）才能再次買入。同一時間只能持有一股。求最大利潤。
解題思路：使用狀態機動態規劃，定義三個狀態來描述每天結束時的情況：
hold：手中持有股票（代表「持股」狀態下的最大利潤）sold：今天剛賣出股票（明天必須冷靜，不能買）rest：今天處於冷靜或空倉狀態（可以明天買入）
狀態轉移方程：
hold = max(hold, rest - price)— 繼續持股，或今天從 rest 狀態買入sold = hold + price— 今天賣出手中的股票rest = max(rest, sold)— 繼續休息，或從昨天 sold 狀態轉來
初始值：hold = -prices[0]（第一天買入）、sold = 0、rest = 0。
答案：max(sold, rest)（最終不持股的最大利潤，sold 和 rest 都是不持股的終態）。
此方法每天只需計算三個值，時間 O(n)，空間 O(1)，極為高效。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單次線性遍歷價格陣列，每天只進行常數次計算。
空間複雜度：O(1) — 只使用三個狀態變數 hold、sold、rest，不需要額外陣列。
虛擬碼
1. Initialize hold = -prices[0], sold = 0, rest = 0. 2. For each price from index 1 to n-1: a. Save previous state: prevHold, prevSold, prevRest. b. hold = max(prevHold, prevRest - price) // hold or buy c. sold = prevHold + price // sell today d. rest = max(prevRest, prevSold) // idle or cooldown ends 3. Return max(sold, rest).
其他解法
二維 DP O(n) 時間，O(n) 空間：定義 dp[i][0] = 第 i 天不持股的最大利潤，dp[i][1] = 持股的最大利潤，但需要額外標記昨天是否賣出（即是否處於冷靜期）。可將狀態展開為三個一維陣列（效果同狀態機 DP），空間可壓縮至 O(1)。
遞迴 + Memoization：定義 dp(i, state) 為第 i 天處於 state（持股/不持股/冷靜）時的最大利潤，用哈希表快取結果。有 O(n) 個子問題，每個 O(1) 計算，總複雜度 O(n)。邏輯清晰但有額外的遞迴開銷。
延伸思考
- 若冷靜期改為 k 天（而非固定 1 天），狀態機需要新增哪些狀態？時間複雜度如何變化？
- 本題允許無限次買賣（受冷靜期限制）。若最多只能進行 2 次交易（LeetCode 123），應如何調整 DP 設計？
- 若在每次買入時需支付固定手續費（LeetCode 714），該如何在現有的狀態轉移方程中加入手續費的影響？