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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.