> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md).

# 0714. 买卖股票的最佳时机含手续费

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

<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:

```python

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 表示当前有股票

和上面不同的是，上面使用返回值表示不同状态，而这里是用参数表示不同状态。大家可以根据自己的喜好选择不同的写法。

```py
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

#### 思路

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

#### 关键点

* 滚动数组优化技巧

#### 代码

* 语言支持：Python3

Python3 Code:

```py

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 数组的好处就是可以使用滚动数组优化。比如这道题使用滚动数组可将空间进一步压缩。

```py
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)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/mzctl2.jpg)