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:


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

思路

使用 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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

上一页0710. 黑名单中的随机数下一页0718. 最长重复子数组

最后更新于1年前