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

我心飞翔 分类:javascript

本文正在参与掘金团队号上线活动,点击 查看详情

一、题目描述:

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

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])

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

例子1:

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

初始状态如下图:
image.png
开始循环:

image.png

image.png

image.png

image.png

image.png

最后,卖出最大利润为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]
};
 

四、总结:

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

回复

我来回复
  • 暂无回复内容