714. 买卖股票的最佳时机含手续费｜刷题打卡

一、题目描述：

给定一个整数数组 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.

注意：

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

二、思路分析：

在之前买卖股票的最佳时机题中，增加了含有手续费，并且不限制购买次数。

此时，我们需要思考的是，当天的利润最大多少。

那么就会有两种情况：一种是今天持有，一种是今天不持有的情况。

最值情况可以使用动态规划：

我们可以定义两个dp数组，一个是不持有的dp1，一个是持有的dp2。两个数组初始值均为0。对于持有的，在刚开始需要持有股票，那么dp2[0] = -prices[0]。

找关系

dp1：从i= 1天开始遍历prices。在遍历prices时，对于不持有股票的dp1而言，当天的利润应该分两种情况：

• 昨天持有。今天卖掉。即：dp2[i-1] + prices[i] - fee。(dp2[i-1]为截至昨天的利润，可能为负，卖掉今天的价格属于收入，再减去手续费)
• 昨天不持有的。即：dp1[i-1]

此时dp1[i]应该取两者的最大值。

dp1[i]=Math.max(dp1[i−1],dp2[i−1]+prices[i]−fee)dp1[i] = Math.max(dp1[i-1], dp2[i-1] + prices[i] - fee)dp1[i]=Math.max(dp1[i−1],dp2[i−1]+prices[i]−fee)

dp2：对于持有股票的dp2而言，当天的利润应该分两种情况：

• 昨天持有。即：dp2[i - 1]
• 昨天不持有。 今天持有。即：dp2[i-1] - prices[i]。(dp2[i-1]为截至昨天的不持有最大利润，再买入今天股票的价格)

此时dp2[i]也应该取两者的最大值。

dp2[i]=Math.max(dp2[i−1],dp1[i−1]−prices[i])dp2[i] = Math.max(dp2[i - 1], dp1[i - 1] - prices[i])dp2[i]=Math.max(dp2[i−1],dp1[i−1]−prices[i])

最后返回当天不持有的最大利润即可。

例子1：

prices = [1,3,2,8,4,5], fee = 2

初始状态如下图：

开始循环：

最后，卖出最大利润为5。

三、AC 代码：

function maxProfit(prices: number[], fee: number): number {
    let dp1 = new Array(prices.length).fill(0) // 不持有
    let dp2 = new Array(prices.length).fill(0) //持有
    dp2[0] = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        dp1[i] = Math.max(dp1[i - 1], prices[i] + dp2[i - 1] - fee)
        dp2[i] = Math.max(dp2[i - 1], dp1[i - 1] - prices[i])
    }
    return dp1[prices.length - 1]
};

四、总结：

遇到求最大值或最小值时，可以多考虑动态规划。求最值问题是属于动态规划的常见一类题型。

作者：ClyingDeng

链接：https://juejin.cn/post/6948708063621120030

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。