714. Best Time to Buy and Sell Stock with Transaction Fee

Leetcode link

题目简介

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */

题目给我们一个数字数组 prices 代表一只股票每天的股价；数字 fee 代表交易股票的手续费（一次买卖交易只扣一次）

要求我们选择合适的买卖时机使得收益最大化（同一天不允许同时买卖）

返回最终收益

解题思路

我们可以把每天的决策拆分为两种：持有/买入股票 & 卖出股票/持有现金

两种决策在 T0 以及 T1 的状态变化如下：

解释一下：

• 在 T0（初始状态）时：假设我们选择了 cash 由于我们手上没有股票，所以也没有卖出收益，此时为 0；假设我们选择 hold，此时我们的收益是 -prices[0]（因为我们拿现金买入了该股票，所以现在收益为负）
• 在 T1 时：如果我们现在要选择 cash，那么我们要判断在 T0 时选择 cash 以及选择 hold 两种策略下的最大收益；如果我们要选择 hold 也同理

接下来解释一下状态转移方程

对于 T1 选 cash 的情况来说：

• 如果 T0 也选择持有现金 cash，则当前收益为 T0 的 cash（因为现金都没动，延续前一天收益）
• 如果 T0 选择买入股票 hold，则我们需要卖出股票，此时的收益为 hold+prices[i] - fee（hold 代表之前买股票的钱，prices[i] 代表股票当前价格，fee 代表交易股票手续费。由于 hold 在 T0 的时候为 负，所以相当于是之前借了钱买股票，现在卖股票无息把钱还了）

对于 T1 选 hold 的情况来说：

• 如果 T0 也选择买入股票 hold：相当于我们现在持有股票，收益还是 T0 的 hold（因为股票没动，延续前一天收益）
• 如果 T0 选择持有现金 cash：代表我们买入股票，当前剩余收益就是 cash-prices[i]（因为我们拿之前收益买股票了，收益变少了）

max 是为了取得当下最优策略，我们持续推进状态，直到最后一天选择 cash，就是我们的最终最大收益

Javascript

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function (prices, fee) {
    // the maximum profit we can have while holding a stock
    let hold = -prices[0]
    // the maximum profit we can have without holding a stock
    let cash = 0

    for (let i = 1; i < prices.length; i++) {
        const curPrice = prices[i]
        const prevCash = cash
        // if we sell the stock, we can earn hold + price - fee
        cash = Math.max(cash, hold + curPrice - fee)
        // othervise, if we hold it, we use cash to buy the stock
        hold = Math.max(hold, prevCash - curPrice)
    }

    return cash
};

复杂度分析

时间

O(n)

空间

O(1)