714. Best Time to Buy and Sell Stock with Transaction Fee

Best Time to Buy and Sell Stock with Transaction Fee

題目描述：給定每日股價 prices 與手續費 fee，可進行任意次交易（買賣不重疊），每次賣出需扣除 fee，求最大利潤。

解題思路：動態規劃：定義 hold（持股時的最大現金）與 cash（不持股時的最大現金）。每天更新：hold = max(hold, cash - price)（繼續持有或今日買入）；cash = max(cash, hold + price - fee)（繼續不持股或今日賣出扣費）。空間 O(1)，一次線性掃描。

時間複雜度：O(n) — 只需一次線性掃描所有股價。

空間複雜度：O(1) — 只保留 cash 和 hold 兩個變數，不需 DP 陣列。

貪心法：模擬「盡量持有上漲趨勢的股票」——買入時記錄成本 buy = price + fee，當 price > buy 時累積利潤並允許「回補」（調整 buy = price）。等價於 DP 但思路不同，實作較不直觀。

完整 DP 陣列：dp[i][0] / dp[i][1] 分別存第 i 天不持股/持股的最大利潤，佔 O(n) 空間，但便於回溯交易路徑。

1. 若限制最多 k 次交易（LC 188），狀態轉移方程式需如何增加維度？
2. 若手續費改為按比例（如 1%），整數 DP 方法是否仍適用？
3. 若加入「冷卻期」（賣出後次日不能買入，LC 309），hold 和 cash 的狀態如何擴展？