https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
给定一个整数数组 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.
- 动态规划
- 暂无
首先明确一点。 如果没有交易费用，那么和另一道力扣的简单难度题目一样。 多了交易费用导致问题稍微复杂了一点。加了交易费用有什么不同呢？
举一个例子大家就明白了。 比如 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:
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
def dp(i):
if i == 0:
return 0, -prices[0] - fee
sell, buy = dp(i - 1)
return max(sell, buy + prices[i]), max(buy, sell - prices[i] - fee)
return dp(len(prices) - 1)[0]另一种写法的记忆化递归。
f(i, state) 表示第 i 天（i 从 0 开始）以 state 的状态的最大利润。
- state 为 0 表示当前没股票
- state 为 1 表示当前有股票
和上面不同的是，上面使用返回值表示不同状态，而这里是用参数表示不同状态。大家可以根据自己的喜好选择不同的写法。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
@lru_cache(None)
def dp(i, state):
if i == len(prices) - 1:
return prices[i] - fee if state == 1 else 0
if state == 1:
return max(dp(i + 1, 1), dp(i + 1, 0) + prices[i] - fee)
return max(dp(i + 1, 0), dp(i + 1, 1) - prices[i])
return dp(0, 0)复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
使用 dp 的思路和上面一样，只是代码形式不同而已。
- 滚动数组优化技巧
- 语言支持：Python3
Python3 Code:
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for i in range(2)]] * n
for i in range(n):
if i == 0:
dp[i][0] = 0
dp[i][1] = -1 * prices[i]
else:
dp[i][0] = max(dp[i - 1][1] + prices[i] - fee, dp[i - 1][0])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[-1][0]复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
使用 DP 数组的好处就是可以使用滚动数组优化。比如这道题使用滚动数组可将空间进一步压缩。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
# [手里没股票, 手里有股票]
dp = [0, 0]
for i in range(n):
if i == 0:
dp[0] = 0
dp[1] = -1 * prices[i] - fee
else:
dp[0] = max(dp[0], dp[1] + prices[i])
dp[1] = max(dp[1], dp[0] - prices[i] - fee)
return dp[0]复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
