題目：你是一位股票投資人，給定一個陣列 prices，其中第 i 個元素是第 i 天的股價。
你可以多次買入和賣出，但有一個 限制：

• 賣出後的隔一天，不能立即買入（必須休息一天）。
• 要求最大獲利
• 

解法一

• 動態規劃（DP，狀態機解法）

註解

• hold[i]：第 i 天結束後，手上 持有股票 的最大獲利
• sold[i]：第 i 天結束後，剛賣出股票 的最大獲利
• rest[i]：第 i 天結束後，休息 的最大獲利

狀態轉移
1. 持股：

• 昨天已經持股 → 今天繼續持股
• 昨天休息 → 今天買股票
  hold[i] = max(hold[i-1], rest[i-1] - prices[i])
  2. 剛賣出：
• 今天賣掉昨天的股票
  sold[i] = hold[i-1] + prices[i]
  3. 休息：
• 昨天也在休息 → 今天繼續休息
• 昨天剛賣出 → 今天被迫休息（冷卻期）
  rest[i] = max(rest[i-1], sold[i-1])

解法二

• 優化 DP（空間壓縮）
• 只記錄前一天的狀態，將空間複雜度從 O(n) 降到 O(1)

總結

• 這題是在 Day 13 的基礎上增加「冷卻期」
• 多了一個 rest 狀態，確保賣出後必須休息一天
• 面試時最常用的寫法是 DP 狀態機（方法二優化版也要會）