題目目錄Best Time to Buy and Sell Stock with Cooldown

每天只看昨天的三種狀態，賣出後必須冷卻一天。

TIME O(n)空間 O(n)：三個 DP 陣列

01 / 逐日狀態轉移INITIALIZE

i—

prices[i]—

更新中—

價格與 DP 表每一欄是一天；橘色是正在計算的格子

狀態機粗橘線是 max() 選中的轉移

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：三種狀態代表什麼？

每一天結束時，你只會處在三種狀態之一。

buy[i]：第 i 天結束時手上持有股票的最大利潤（今天買入，或之前買了繼續持有）。

sell[i]：第 i 天結束時手上沒有股票、且到目前為止最好的賣出收益。今天賣出要從 buy[i − 1] 加上今天的價格。

rest[i]：第 i 天結束時沒有股票、可以在明天買入。昨天剛賣（sell[i − 1]）的人今天只能休息，所以 buy 只能從 rest 轉移過來，這就是冷卻期。

rest 的 max 裡多放了 buy[i − 1]：因為 buy[i] ≤ rest[i] 恆成立，它從不會勝出，答案仍然正確，只是一個多餘的候選。

時間 O(n)，空間 O(n)；每天只用到前一天，可以再壓縮成三個變數達到 O(1)。