动态规划中等1 种解法
#714买卖股票的最佳时机含手续费
交易次数不限，每笔完整交易收取一次手续费，求最大利润。
#数组#动态规划#贪心#股票
原题
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
提示：
1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104
解题主线
- 每天结束只需记录不持股与持股两种最大现金，卖出时统一扣除一次手续费。
- 手续费放在买入或卖出转移都可以，但只能选择一处扣除，不能重复收费。
- 更新持股状态时必须使用前一天的不持股现金，清晰避免同一天新卖出状态被再次买入。
解法 1：两状态动态规划
cash 表示当天结束后不持股的最大现金，hold 表示持股的最大现金；卖出转移时扣除 fee，并用旧状态同步更新。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length < 2) {
return 0;
}
// cash 与 hold 分别表示当天结束后不持股、持股的最大现金。
int cash = 0;
int hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
// 使用旧状态同步转移，避免本轮更新相互污染。
int previousCash = cash;
int previousHold = hold;
// 手续费统一在卖出时扣除，每笔完整交易只收费一次。
cash = Math.max(previousCash, previousHold + prices[i] - fee);
hold = Math.max(previousHold, previousCash - prices[i]);
}
return cash;
}
}边界与易错点
- 旧源码注释链接误指向第 309 题冷冻期；本题没有冷冻限制，真实题号为 714。
- 不能对每一天或买卖两端都扣手续费，一笔交易只收费一次。
- 价格波动带来的毛利润不超过手续费时，应保持原状态而不是强制交易。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/greedy/Q714_maxStockProfit_fee.java