买卖股票的最佳时机（含手续费）

状态机 DP 经典题：在买入或卖出时扣手续费，核心仍是持股 / 不持股状态转移。

#resource / algorithm #type / snippet #status / growing #source / leetcode #algo / dp

[!info] related notes 动态规划区间 DP 与状态机 DP 买卖股票的最佳时机

买卖股票的最佳时机（含手续费）

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

状态

hold：持股最大收益
empty：不持股最大收益

转移

empty = max(empty, hold + price - fee)
hold = max(hold, empty - price)

JavaScript

var maxProfit = function(prices, fee) {
    let hold = -prices[0];
    let empty = 0;

    for (let i = 1; i < prices.length; i++) {
        const prevEmpty = empty;
        empty = Math.max(empty, hold + prices[i] - fee);
        hold = Math.max(hold, prevEmpty - prices[i]);
    }

    return empty;
};