714. 买卖股票的最佳时机含手续费
题目描述
输入整数数组 prices 和整数 fee。prices[i] 是第 i 天的股价，fee 是每笔交易的手续费。
一笔交易指先买入一股、之后再卖出的完整过程，每完成一笔就扣一次 fee。交易次数不限，但手里最多只能有一股：必须先卖掉手中的股票，才能再买。
返回能获得的最大总利润。不交易时利润为 0。
输入：prices = [1,3,2,8,4,9], fee = 2 输出：8
解释：第 0 天买、第 3 天卖赚 8-1-2=5；第 4 天买、第 5 天卖赚 9-4-2=3，合计 8。
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
数据范围
1 <= prices.length <= 5 * 10^41 <= prices[i] < 5 * 10^40 <= fee < 5 * 10^4
解题思路：动态规划（双状态）
每天结束时只有两种状态：cash（不持股时的最大利润）和 hold（持股时的最大利润）。第一天 cash = 0，hold = -prices[0]。之后每天：cash = max(cash, hold + p - fee)，即保持空仓或今天卖出并付手续费；hold = max(hold, cash - p)，即继续持有或今天买入。两个新值都要用昨天的旧值计算。
为什么正确
处理完第 i 天后，cash 与 hold 分别是前 i 天结束时空仓 / 持仓能达到的最大利润。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
手续费每笔交易只扣一次，不要在买入和卖出时各扣一次。更新顺序上，如果先算出新 cash 再用它算 hold，等于允许同一天卖出又买入。这对本题不会出错（会多付手续费），但同时赋值更清晰。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
cash, hold = 0, -prices[0]
for p in prices[1:]:
cash, hold = max(cash, hold + p - fee), max(hold, cash - p)
return cashclass Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
int p = prices[i];
int nc = Math.max(cash, hold + p - fee), nh = Math.max(hold, cash - p);
cash = nc; hold = nh;
}
return cash;
}
}class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int cash = 0, hold = -prices[0];
for (size_t i = 1; i < prices.size(); i++) {
int p = prices[i];
int nc = max(cash, hold + p - fee), nh = max(hold, cash - p);
cash = nc; hold = nh;
}
return cash;
}
};func maxProfit(prices []int, fee int) int {
cash, hold := 0, -prices[0]
for _, p := range prices[1:] {
cash, hold = max(cash, hold+p-fee), max(hold, cash-p)
}
return cash
}var maxProfit = function(prices, fee) {
let cash = 0, hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
[cash, hold] = [Math.max(cash, hold + p - fee), Math.max(hold, cash - p)];
}
return cash;
};function maxProfit(prices: number[], fee: number): number {
let cash = 0, hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
[cash, hold] = [Math.max(cash, hold + p - fee), Math.max(hold, cash - p)];
}
return cash;
}其他解法
动态规划用两个状态机械地转移，容易推广到其他股票题；贪心直接维护最低成本，代码相近但依赖一个巧妙的反悔技巧。
解法 2：贪心（延迟卖出） 时间 O(n)，空间 O(1)
用 buy 记录含手续费的最低买入成本，初值为 prices[0] + fee。遇到 p + fee < buy 时更新 buy = p + fee。遇到 p > buy 时先把 p - buy 计入利润，再令 buy = p。这样以后价格继续上涨时可以接着赚差价，相当于反悔这次卖出而不重复付手续费。
和动态规划同样是 O(n) 时间、O(1) 空间。关键在于 buy = p 这一步的“反悔”含义，不易想到，也不容易推广到冷冻期等变体。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
buy = prices[0] + fee
profit = 0
for p in prices[1:]:
if p + fee < buy:
buy = p + fee
elif p > buy:
profit += p - buy
buy = p
return profitclass Solution {
public int maxProfit(int[] prices, int fee) {
int buy = prices[0] + fee, profit = 0;
for (int i = 1; i < prices.length; i++) {
int p = prices[i];
if (p + fee < buy) {
buy = p + fee;
} else if (p > buy) {
profit += p - buy;
buy = p;
}
}
return profit;
}
}class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int buy = prices[0] + fee, profit = 0;
for (int i = 1; i < (int)prices.size(); i++) {
int p = prices[i];
if (p + fee < buy) {
buy = p + fee;
} else if (p > buy) {
profit += p - buy;
buy = p;
}
}
return profit;
}
};func maxProfit(prices []int, fee int) int {
buy, profit := prices[0]+fee, 0
for _, p := range prices[1:] {
if p+fee < buy {
buy = p + fee
} else if p > buy {
profit += p - buy
buy = p
}
}
return profit
}var maxProfit = function(prices, fee) {
let buy = prices[0] + fee, profit = 0;
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
if (p + fee < buy) {
buy = p + fee;
} else if (p > buy) {
profit += p - buy;
buy = p;
}
}
return profit;
};function maxProfit(prices: number[], fee: number): number {
let buy = prices[0] + fee, profit = 0;
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
if (p + fee < buy) {
buy = p + fee;
} else if (p > buy) {
profit += p - buy;
buy = p;
}
}
return profit;
}