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

链接：714.买卖股票的最佳时机含手续费
难度：Medium
标签：贪心、数组、动态规划
简介：给定一个整数数组  prices，其中第  i  个元素代表了第  i  天的股票价格 ；非负整数  fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

题解 1 - typescript

• 编辑时间：2020-12-17
• 执行用时：452ms
• 内存消耗：67.9MB
• 编程语言：typescript
• 解法介绍：动态规划。

function maxProfit(prices: number[], fee: number): number {
  const len = prices.length;
  /**
   * 0 手上无股票
   * 1 手上有股票
   */
  const dp: number[][] = new Array(len).fill(0).map(_ => new Array(2).fill(0));
  dp[0] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    dp[i] = [
      Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee),
      Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]),
    ];
  }
  return dp[len - 1][0];
}

题解 2 - typescript

• 编辑时间：2020-12-17
• 执行用时：116ms
• 内存消耗：48.1MB
• 编程语言：typescript
• 解法介绍：完善题解 1。

function maxProfit(prices: number[], fee: number): number {
  /**
   * 0 手上无股票
   * 1 手上有股票
   */
  let price0 = 0;
  let price1 = -prices[0];
  for (let i = 1, len = prices.length; i < len; i++) {
    [price0, price1] = [
      Math.max(price0, price1 + prices[i] - fee),
      Math.max(price1, price0 - prices[i]),
    ];
  }
  return price0;
}
console.log(maxProfit([9, 8, 7, 1, 2], 3));

题解 3 - typescript

• 编辑时间：2021-09-13
• 执行用时：280ms
• 内存消耗：64.8MB
• 编程语言：typescript
• 解法介绍：动态规划。

function maxProfit(prices: number[], fee: number): number {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(_ => new Array(2).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
  }
  return dp[n - 1][1];
}

题解 4 - typescript

• 编辑时间：2021-09-13
• 执行用时：108ms
• 内存消耗：47.6MB
• 编程语言：typescript
• 解法介绍：动态规划优化。

function maxProfit(prices: number[], fee: number): number {
  const n = prices.length;
  const dp = new Array(2).fill(0).map(_ => new Array(2).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < n; i++) {
    const idx = i % 2;
    const preIdx = idx ^ 1;
    dp[idx][0] = Math.max(dp[preIdx][0], dp[preIdx][1] - prices[i]);
    dp[idx][1] = Math.max(dp[preIdx][1], dp[preIdx][0] + prices[i] - fee);
  }
  return dp[(n - 1) % 2][1];
}

题解 5 - python

• 编辑时间：2023-10-06
• 执行用时：516ms
• 内存消耗：28.4MB
• 编程语言：python
• 解法介绍：同122题。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        # [i][0] i天买， [i][1] i天卖
        dp = [[-inf for _ in range(2)] for _ in range(n)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        res = 0
        num1 = 0
        num2 = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i][0], num1 - prices[i])
            dp[i][1] = max(dp[i][1], num2 + prices[i] - fee)
            res = max(res, dp[i][0], dp[i][1])
            num1 = max(num1, dp[i][1])
            num2 = max(num2, dp[i][0])
        return res