题目链接

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

题目描述

image.png

实现代码

动态规划思想

动态规划思想：跟买卖股票的最佳时机含冰冻期一样，每个i位置时刻只有两种情况，就是持有股票和不持有股票，因此可以设置如下两个状态：

  1. f[i][0]：在i位置不持有股票的最大利润
  2. f[i][1]：在i位置持有股票的最大利润

我们假设手续费在卖出的时候进行扣除，买入的时候不做计算

两个状态与第i-1位置的状态对应的状态转移方程如下：

  1. f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i] - fee)
  2. f[i][1] = max(f[i-1][1], f[i-1][0] - prices[i])

对应的实现代码如下：

  1. class Solution:
  2.     def maxProfit(self, prices: List[int], fee: int) -> int:
  3.         n = len(prices)
  4.         dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]
  5.         for i in range(1, n):
  6.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
  7.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  8.         return dp[n - 1][0]

贪心思想

贪心思想：我们记buy表示每次获得最大利润的时候的买入价格，这里我们将手续费算在买入价格里，因此初始化buy = prices[i] + fee，因此对于遍历的每个位置i的有如下几种情况：

  1. prices[i] + fee < buy时：我们可以用更低的价格买入股票，因此更新buy
  2. prices[i] > buy时：我们可以将股票卖出，获取利润，同时将buy更新为prices[i]，因为这可能并非当前最优卖出位置，同时即便是当前最优位置，我们还要找到下一个买入的最佳时机

这里需要注意，对于找到一次最佳买卖时机后，下一次进入买入，价格应该是跟前一次卖出的价格进行比较，如果当前价格加上手续费都比上一次最佳买卖时机的卖出价格低，那么就可以进行买入，因为一定相对于上次不卖出而言赚的更多

实现代码如下：

  1. class Solution:
  2.     def maxProfit(self, prices: List[int], fee: int) -> int:
  4.         n = len(prices)
  5.         if n==1:
  6.             return 0
  8.         profit = 0
  9.         buy = prices[0] + fee
  11.         for i in range(1, n):
  12.             price = prices[i]
  13.             if price + fee < buy:
  14.                 buy = price + fee
  15.                 continue
  16.             elif price > buy:
  17.                 profit += price - buy
  18.                 buy = price
  19.                 continue
  21.         return profit