动态规划中等1 种解法

#714买卖股票的最佳时机含手续费

交易次数不限，每笔完整交易收取一次手续费，求最大利润。

#数组#动态规划#贪心#股票

解题主线

每天结束只需记录不持股与持股两种最大现金，卖出时统一扣除一次手续费。

手续费放在买入或卖出转移都可以，但只能选择一处扣除，不能重复收费。

更新持股状态时必须使用前一天的不持股现金，清晰避免同一天新卖出状态被再次买入。

解法 1：两状态动态规划

cash 表示当天结束后不持股的最大现金，hold 表示持股的最大现金；卖出转移时扣除 fee，并用旧状态同步更新。

时间复杂度

O(n)

空间复杂度

O(1)

714. 买卖股票的最佳时机含手续费 · 两状态动态规划

java

final class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        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;
    }
}

cash 表示当天结束后不持股的最大现金，hold 表示持股的最大现金；卖出转移时扣除 fee，并用旧状态同步更新。

边界与易错点

旧源码注释链接误指向第 309 题冷冻期；本题没有冷冻限制，真实题号为 714。
不能对每一天或买卖两端都扣手续费，一笔交易只收费一次。
价格波动带来的毛利润不超过手续费时，应保持原状态而不是强制交易。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q714_maxStockProfit_fee.java