714. Best Time to Buy and Sell Stock with Transaction Fee
714. Best Time to Buy and Sell Stock with Transaction Fee
交易次數無限，但每完成一筆交易要付 fee 的手續費。
思路
這一題改的旋鈕是「每筆交易扣手續費」，交易次數仍然無限。 完整的狀態機和其他五題的對照見 股票買賣家族模板。
從 122 出發，唯一要改的是在轉移式裡把 fee 減掉：
buys[i] = max(buys[i-1], sells[i-1] - prices[i] - fee) # 買進時就先付掉手續費
在買進時扣還是賣出時扣？ 兩種都對，只要整份程式碼只扣一次就好。
- 買進時扣（這裡的寫法）：一買進就把手續費認列成成本
- 賣出時扣：
sells[i] = max(sells[i-1], buys[i-1] + prices[i] - fee)
差別只在中間狀態的數值，最終答案相同。買進時扣有個小好處：sells 的語意保持乾淨（就是「手上沒股票時的獲利」），不用記得它有沒有被扣過。
手續費改變了什麼
122 的貪心解（「把所有上漲區段吃下來」）在這題不成立。因為每拆一筆交易就多付一次手續費，a → b → c 拆成兩筆要付兩次費，可能還不如一次做完。
所以手續費的作用是懲罰頻繁交易，讓「要不要現在賣掉」變成一個真的要權衡的決定 —— 這正是狀態機存在的意義。這也是為什麼加了任何限制（冷凍期、手續費、次數上限）就必須回到 DP。
不過這題還是有貪心解，只是比 122 複雜：記住「有效買入價」，只在 price > buy + fee 時才賣，並在賣出後把買入價設成 price - fee 以允許連續上漲繼續累積。想得出來很漂亮，但推導比 DP 難，面試時給 DP 版比較穩。
解題方向
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if len(prices) < 2:
return 0
buys = [float('-inf')] * len(prices)
sells = [0] * len(prices)
for i in range(len(prices)):
if i == 0:
buys[i] = max(buys[i], 0 - prices[i] - fee)
else:
buys[i] = max(buys[i-1], sells[i-1] - prices[i] - fee)
sells[i] = max(sells[i-1], buys[i-1] + prices[i])
return sells[-1]
和 122 逐字比對，只差 - fee 那兩處。這就是把家族當成一個狀態機來記的好處：新題目來了只要問「規則改了哪一項」，然後改對應的那一行。
buys 初始化成 -inf 是哨兵（「還沒開始就持有股票」不是合法狀態），第 0 天的 -prices[0] - fee 則是真正的起點。
兩個陣列可以省成兩個變數，因為轉移只看前一天：
buys, sells = float('-inf'), 0
for price in prices:
buys = max(buys, sells - price - fee)
sells = max(sells, buys + price)
return sells
和 122 一樣，sells 用到同一輪剛更新的 buys 是無害的 —— 那代表「今天買今天賣」，獲利是 -fee，只會更差，max 不會選它。（309 冷凍期 那題就不能這樣寫。）
補充
整個家族的對照見 股票買賣家族模板。這題和 122、309 是同一組（k 無限），三題的程式碼幾乎一樣：
| 買進轉移 | |
|---|---|
| 122 | max(buys, sells - price) |
| 309 | max(buys, sells_前天 - price) |
| 714 這題 | max(buys, sells - price - fee) |
一起看最有效率 —— 三題其實是同一題的三種微調。
複雜度
- 時間 — 一趟迴圈，每天常數次計算
- 空間 用陣列、 用滾動變數
其中 n 是天數。手續費不影響複雜度，只影響轉移式裡的一個常數項。