第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0714. 买卖股票的最佳时机含手续费

题目地址(714. 买卖股票的最佳时机含手续费)

题目描述

1
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
2
3
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
4
5
返回获得利润的最大值。
6
7
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
8
9
示例 1:
10
11
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
12
输出: 8
13
解释: 能够达到的最大利润:
14
在此处买入 prices[0] = 1
15
在此处卖出 prices[3] = 8
16
在此处买入 prices[4] = 4
17
在此处卖出 prices[5] = 9
18
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
19
20
注意:
21
22
0 < prices.length <= 50000.
23
0 < prices[i] < 50000.
24
0 <= fee < 50000.
Copied!

前置知识

  • 动态规划

公司

  • 暂无

记忆化递归

思路

首先明确一点。 如果没有交易费用,那么和另一道力扣的简单难度题目一样。 多了交易费用导致问题稍微复杂了一点。加了交易费用有什么不同呢?
举一个例子大家就明白了。 比如 prices = [1,1,2,2,6] fee = 3。 如果没有按照无交易费的原则只要有利可图就交易,那么我们的收益为 1。实际上,在 1 买入, 6 卖出却可以得到 3 的收益。其根本原因在于交易次数对结果是有影响的
这道题不能使用上述的贪心策略,而必须使用动态规划。
动态规划和贪心有着很强的关联性。
定义 dp[i] 为到第 i 天(0=< i <n)为止的收益,那么答案就是 dp[n-1]。但是由于题目限定了只能在手上没有股票的时候才能买,手上有股票的时候才能卖(这很显然)。因此我们需要多定义一个维度的状态,表示现在手上是否有股票。标识是否手上有股票只需要一个长度为 2 的列表就可以了。
因此我们可以使用 dp[i][0] 表示没有股票的情况下的最大利润,dp[i][1] 表示有股票的情况下的最大利润。
那么:
  • 如果第 i 天手上没有股票,要么是 i - 1 没股票,今天什么都不做。要么是 i - 1 手上有股票,今天卖了它。因此 dp[i][0] 就是这两种情况的利润最大值。
  • 如果第 i 天手上有股票,要么是 i - 1 有股票,今天什么都不做。要么是 i - 1 手上没有股票,今天买了它。因此 dp[i][0] 就是这两种情况的利润最大值。
最后返回 dp[n-1][0] 即可。
由于 dp[n-1][1] <= dp[n-1][0] ,因此直接返回 dp[n-1][0] 即可。
base case 见下方代码的递归出口。

关键点

  • 记忆化递归

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def maxProfit(self, prices: List[int], fee: int) -> int:
3
def dp(i):
4
if i == 0:
5
return 0, -prices[0] - fee
6
sell, buy = dp(i - 1)
7
return max(sell, buy + prices[i]), max(buy, sell - prices[i] - fee)
8
9
return dp(len(prices) - 1)[0]
Copied!
另一种写法的记忆化递归。
f(i, state) 表示第 i 天(i 从 0 开始)以 state 的状态的最大利润。
  • state 为 0 表示当前没股票
  • state 为 1 表示当前有股票
和上面不同的是,上面使用返回值表示不同状态,而这里是用参数表示不同状态。大家可以根据自己的喜好选择不同的写法。
1
class Solution:
2
def maxProfit(self, prices: List[int], fee: int) -> int:
3
@lru_cache(None)
4
def dp(i, state):
5
if i == len(prices) - 1:
6
return prices[i] - fee if state == 1 else 0
7
if state == 1:
8
return max(dp(i + 1, 1), dp(i + 1, 0) + prices[i] - fee)
9
return max(dp(i + 1, 0), dp(i + 1, 1) - prices[i])
10
11
return dp(0, 0)
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

DP

思路

使用 dp 的思路和上面一样,只是代码形式不同而已。

关键点

  • 滚动数组优化技巧

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def maxProfit(self, prices: List[int], fee: int) -> int:
3
n = len(prices)
4
dp = [[0 for i in range(2)]] * n
5
for i in range(n):
6
if i == 0:
7
dp[i][0] = 0
8
dp[i][1] = -1 * prices[i]
9
else:
10
dp[i][0] = max(dp[i - 1][1] + prices[i] - fee, dp[i - 1][0])
11
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
12
13
return dp[-1][0]
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
使用 DP 数组的好处就是可以使用滚动数组优化。比如这道题使用滚动数组可将空间进一步压缩。
1
class Solution:
2
def maxProfit(self, prices: List[int], fee: int) -> int:
3
n = len(prices)
4
# [手里没股票, 手里有股票]
5
dp = [0, 0]
6
for i in range(n):
7
if i == 0:
8
dp[0] = 0
9
dp[1] = -1 * prices[i] - fee
10
else:
11
dp[0] = max(dp[0], dp[1] + prices[i])
12
dp[1] = max(dp[1], dp[0] - prices[i] - fee)
13
14
return dp[0]
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。