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

类型：数组

• 714. 买卖股票的最佳时机含手续费 💛

  https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

  ❓ 数组 prices 存储了股票的每日价格，完成一次交易（买入+卖出）需要付手续费 fee，购买股票前先要卖出手里的股票。求最大收益。

  💡 动态规划

  每天交易结束后，有两种可能的状态：手中不持有股票，手中持有一支股票

  dp[i][0] 表示不持有股票的收益，dp[i][1] 表示持有股票的收益。

  转移方程：

  dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)

  dp[i][0] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])

  class Solution:
      def maxProfit(self, prices: List[int], fee: int) -> int:
          if not prices:
              return 0
  
          dp = [[0, -prices[0]]]
          for i in range(1, len(prices)):
              dp.append([
                  max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee),
                  max(dp[i - 1][0] - prices[i], dp[i - 1][1])
              ])
  
          return max(dp[-1])

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 贪心

  class Solution:
      def maxProfit(self, prices: List[int], fee: int) -> int:
          n = len(prices)
          buy = prices[0] + fee # 把手续费算在购买阶段
          profit = 0
          for i in range(1, n):
              if prices[i] + fee < buy:
                  buy = prices[i] + fee
              elif prices[i] > buy:
  								# 假设我们只拿收益，而没有把股票卖出
                  profit += prices[i] - buy
                  buy = prices[i]
          return profit

  时间复杂度：O(n)，空间复杂度：O(1)