LeetCode 714. 买卖股票的最佳时机含手续费
题目描述
题意分析
可以进行多笔交易，但买入下一股之前必须先卖掉手中的股票。每次完整买卖只扣一次手续费，目标是最大化最终收益。手续费会让频繁交易付出额外成本，需要同时考虑继续持有和立即卖出的选择。
解法：持有/不持有状态 DP
核心思路
[!blue]
按当天结束时是否持股定义两个状态：
cash是不持股时的最大累计现金，hold是持有一股时的最大累计现金，已经扣除这股股票的买入成本。hold包含以前交易留下的收益，因此也可能为正。设今天价格为
price，两个状态都从昨天的值转移：
- 今天不持股：昨天已经不持股且今天不操作，或者昨天持股、今天卖出。对应
cash = max(旧 cash, 旧 hold + price - fee)。- 今天持股：昨天已持股且继续持有，或者昨天不持股、今天买入。对应
hold = max(旧 hold, 旧 cash - price)。每种日末状态的合法来源都已列出；到达同一状态后，未来可执行的操作相同，所以只需保留累计现金最大的方案。手续费统一放在卖出转移中扣除，保证每笔交易只收费一次。
第一天不操作得到
cash = 0，买入得到hold = -prices[0]。遍历结束返回cash，对应已经完成交易的收益。始终不交易的方案会一直保留，所以所有交易都无法获利或只有一天时，答案就是 $0$。
解题步骤
- 令
cash = 0、hold = -prices[0]，从第二天开始遍历价格。- 将昨天的
cash保存到preCash。- 用原来的
hold计算今天的cash，比较不操作与卖出后的收益。- 用
preCash计算今天的hold，比较继续持有与买入后的现金。- 扫描结束返回
cash。
代码实现
class Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0;
int hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
// 保存昨天现金，使两个转移都使用上一天状态
int preCash = cash;
// cash 表示不持股，hold 表示持股，手续费在卖出时扣除。
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, preCash - prices[i]);
}
return cash;
}
}
func maxProfit(prices []int, fee int) int {
cash := 0
hold := -prices[0]
for i := 1; i < len(prices); i++ {
// 保存昨天现金，使两个转移都使用上一天状态
preCash := cash
// cash 表示不持股，hold 表示持股，手续费在卖出时扣除。
if hold+prices[i]-fee > cash {
cash = hold + prices[i] - fee
}
if preCash-prices[i] > hold {
hold = preCash - prices[i]
}
}
return cash
}
复杂度分析
- 时间复杂度：$O(n)$，每天处理两个状态。
- 空间复杂度：$O(1)$，仅保存滚动状态与旧值。
关键点总结
[!green]
- 手续费只扣一次，买卖两侧不能重复扣。
preCash保存昨天的空仓收益，让两条转移读取同一天的旧状态。
易错点总结
[!yellow]
- 持仓初值零相当于免费获得一股。
- 买入只用负价格而不继承历史现金，会退化为最多一笔交易。
- 手续费过高时仍强行交易，忽略了保持零收益的选择。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 122. 买卖股票的最佳时机 II | 中等 | 加入手续费后不能把每个正差都当作独立收益，需维护持有与空仓最优状态。 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 同样在基础股票DP中增加交易限制，原题增加冷冻期，本题每笔交易扣费用。 |
| 121. 买卖股票的最佳时机 | 简单 | 以持有状态和交易次数描述每天的最优收益；本题在交易转移时计入手续费，该题只允许一次买卖。 |
| 123. 买卖股票的最佳时机 III | 困难 | 以持有状态和交易次数描述每天的最优收益；本题在交易转移时计入手续费，该题最多完成两笔交易。 |
| 188. 买卖股票的最佳时机 IV | 困难 | 以持有状态和交易次数描述每天的最优收益；本题在交易转移时计入手续费，该题推广到 k 笔交易。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！