题目

题目来源：力扣（LeetCode）

给定一个整数数组 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

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

思路分析

方法一：动态规划

1、定义状态

由于「不能同时参与多笔交易」，因此每天交易结束后只可能存在两种状态：

  • 手里有一支股票
  • 手里没有股票

定义二维数组 dp[i][2]

  • dp[i][0] 表示第 i 天手里没有股票可获得的最大利润 (i 从 0 开始)
  • dp[i][1] 表示第 i 天手里持有一支股票可获得的最大利润 (i 从 0 开始)

2、状态转移方程

  • 不持有股票：dp[i][0] = max(dp[i -1][0], dp[i - 1][1] + prices[i] - fee)

对于今天 (第 i 天) 不持有股票可获得的最大利润，可以从两个状态转移过来：

  • 昨天 (第 i - 1天) 也不持有，利润为 dp[i -1][0]
  • 昨天 (第 i - 1天) 持有，但今天 (第 i 天) 卖出了， 利润为 dp[i - 1][1] + prices[i] - fee

两者取较大值

  • 持有股票：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

对于今天持有股票可获取的最大利润，可以从两个状态转移过来：

  • 昨天也持有，利润为 dp[i - 1][1]
  • 昨天不持有，但今天买入了，利润为 dp[i - 1][0] - prices[i]

两者取较大值

3、状态初始值
对于第 0 天：

  • 不持有股票，可获得利润为 0，即 dp[0][0] = 0
  • 持有股票 (即花了 prices[0] 的钱买入，那么利润为负)，即 dp[0][1] = -prices[0]

4、确定输出值

我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n - 1][0] 的收益必然是大于 dp[n - 1][1] 的，最后的答案即为 dp[n - 1][0]。

代码实现

  1. /**
  2.  * @param {number[]} prices
  3.  * @param {number} fee
  4.  * @return {number}
  5.  */
  6. var maxProfit = function(prices, fee) {
  7.   const n = prices.length;
  8.   // 定义二维数组
  9.   const dp = new Array(n).fill(0).map(v => new Array(2).fill(0));
  10.   // 第 0 天不持有股票的利润
  11.   dp[0][0] = 0;
  12.   // 第 0 天持有股票的利润
  13.   dp[0][1] = -prices[0];
  14.   for (let i = 1; i < n; ++i) {
  15.     // 不持有股票可获得的最大利润，卖出股票需要手续费fee
  16.       dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
  17.       // 持有股票可获得的最大利润
  18.       dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  19.   }
  20.   // 部交易结束后，持有股票的收益一定低于不持有股票的收益，
  21.   // 因此这时候 dp[n - 1][0] 的收益必然是大于 dp[n - 1][1] 的，
  22.   // 最后的答案即为 dp[n - 1][0]
  23.   return dp[n - 1][0];
  24. };

空间优化

在上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i - 1][0] 和 dp[i - 1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 i + 1天的状态转移即可。

  1. /**
  2.  * @param {number[]} prices
  3.  * @param {number} fee
  4.  * @return {number}
  5.  */
  6. var maxProfit = function (prices, fee) {
  7.   const n = prices.length;
  8.   // sell 不持有股票可获得的利润
  9.   // buy  持有股票可获得的利润
  10.   let [sell, buy] = [0, -prices[0]];
  11.   for (let i = 1; i < n; i++) {
  12.     // Math.max(sell, buy + prices[i] - fee) 不持有股票可获得的最大利润，卖出股票需要手续费fee
  13.     // Math.max(buy, sell - prices[i])  持有股票可获得的最大利润
  14.     [sell, buy] = [Math.max(sell, buy + prices[i] - fee), Math.max(buy, sell - prices[i])]
  15.   }
  16.   // 部交易结束后，持有股票的收益一定低于不持有股票的收益，
  17.   // 因此这时候 dp[n - 1][0] 的收益必然是大于 dp[n - 1][1] 的，
  18.   // 最后的答案即为 dp[n - 1][0]
  19.   return sell;
  20. };

方法二：贪心思想

在方法一中，我们将手续费放在卖出时进行计算。如果我们换一个角度考虑，将手续费放在买入时进行计算，那么就可以得到一种基于贪心的方法。

在「买卖股票的最佳时机 II」中，由于没有手续费，我们的策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。但是本题中由于有手续费，我们就要考虑什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。

我们用 buy 表示在最大化收益的前提下，如果我们手上拥有一支股票，那么它的最低买入价格是多少。在初始时，buy 的值为 prices[0] 加上手续费 fee。

遍历股票交易日价格列表，当我们遍历到第 i (i > 0) 天时，考虑三种情况：

  • 如果当前的股票价格prices[i] 加上手续费fee 小于 手上股票的买入价格buy，我们与其使用 buy 的价格购买股票，不如以更低的价格 prices[i] + fee 的价格买入股票，因此我们将 buy 更新为 prices[i] + fee ；

  • 如果当前的股票价格prices[i] 大于我们手上股票的买入价格buy，那么我们应该卖出股票并获取 prices[i] - buy 的利润。但实际上，我们此时卖出股票可能并不是全局最优的（例如下一天股票价格继续上升），因此我们可以提供一个反悔操作，看成当前手上拥有一支买入价格为 prices[i] 的股票，将 手上股票的价格buy 更新为 prices[i]。这样一来，如果下一天股票价格继续上升，我们会获得 prices[i + 1] - prices[i] 的收益，加上这一天 prices[i] - buy 的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益；

  • 对于其余的情况，当前股票价格prices[i] 落在区间 [buy - fee, buy] 内，它的价格没有低到我们放弃手上的股票去选择它，也没有高到我们可以通过卖出获得收益，因此我们不进行任何操作 (不买不卖)。

代码实现

  1. /**
  2.  * @param {number[]} prices
  3.  * @param {number} fee
  4.  * @return {number}
  5.  */
  6. var maxProfit = function (prices, fee) {
  7.   const n = prices.length;
  8.   // buy 表示在最大化收益的前提下，如果我们手上拥有一支股票，它的最低买入价格
  9.   let buy = prices[0] + fee;
  10.   // 利润
  11.   let profit = 0;
  12.   for (let i = 1; i < n; i++) {
  13.     // 当前的股票价格prices[i] 加上手续费fee < 手上股票的买入价格buy
  14.     // 将 buy 更新为 prices[i] + fee
  15.     // 相当于是以 prices[i] + fee 的价格买入股票
  16.     if (prices[i] + fee < buy) {
  17.       buy = prices[i] + fee;
  18.     } else if (prices[i] > buy) {
  19.       // 当前的股票价格 prices[i] 大于 手上股票的买入价格buy
  20.       // 直接卖出股票并且获得 prices[i] − buy 的收益
  21.       profit += prices[i] - buy;
  22.       // 实际上，我们此时卖出股票可能并不是全局最优的（例如下一天股票价格继续上升），
  23.       // 因此我们可以提供一个反悔操作，看成当前手上拥有一支买入价格为 prices[i] 的股票，将 buy 更新为 prices[i]
  24.       buy = prices[i];
  25.     }
  26.   }
  27.   // 在遍历完整个数组 prices 之后，得到最大的总收益
  28.   return profit;
  29. };

参考阅读 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-han-sh-rzlz/ https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/jian-dan-dpmiao-dong-gu-piao-mai-mai-by-tejdo/ https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/dong-tai-gui-hua-by-liweiwei1419-6/