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

股票交易 冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  1. 输入: prices = [1,2,3,0,2]
  2. 输出: 3 
  3. 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

方法一：动态规划
思路与算法

我们用 f[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：

  • 我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
  • 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
  • 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]。

    这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。

如何进行状态转移呢？在第 i 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i 天的状态会从第 i-1 天的状态转移而来；我们也可以不进行任何操作，此时第 i 天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：

  • 对于 f[i][0]，我们目前持有的这一支股票可以是在第 i-1i−1 天就已经持有的，对应的状态为 f[i-1][0]；或者是第 i 天买入的，那么第 i-1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1][2] 加上买入股票的负收益 - prices[i]。因此状态转移方程为：

image.png

  • 对于 f[i][1]，我们在第 ii 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 f[i−1][0] 加上卖出股票的正收益 + prices[i]。因此状态转移方程为：

image.png

  • 对于 f[i][2]，我们在第 ii 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i-1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1][1]；如果不处于冷冻期，对应的状态为 f[i-1][2]。因此状态转移方程为：

image.png
这样我们就得到了所有的状态转移方程。如果一共有 nn 天，那么最终的答案即为：
image.png
注意到如果在最后一天（第 n-1 天）结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是 f[n-1][1] 和 f[n-1][2] 中的较大值，即：
image.png
细节
我们可以将第 00 天的情况作为动态规划中的边界条件：
image.png

  1. public int maxProfit(int[] prices) {
  2.     if (prices == null || prices.length == 0) return 0;
  3.     int len = prices.length;
  4.     // dp[i][0] : 持有股票
  5.     // dp[i][1] : 不持有股票，本日卖出，下一天为冷冻期
  6.     // dp[i][2] : 不持有股票，本日无卖出，下一天非冷冻期
  7.     int[][] dp = new int[len][3];
  9.     //初始状态:
  10.     // 1: 第一天持有，只有可能是买入
  11.     dp[0][0] = -prices[0];
  13.     // 其实dp[0][1]、dp[0][2] 都不写，默认为0也对
  14.     // 2. 第0天，相当于当天买入卖出，没有收益，并造成下一天冷冻期，减少选择。综合认为是负收益
  15.     dp[0][1] = Integer.MIN_VALUE;
  17.     // 3. 相当于没买入，收益自然为0
  18.     dp[0][2]=0;
  20.     for (int i = 1; i < len; i++) {
  21.       // 持有股票： 1.昨天持有股票 2.本日买入（条件：昨天不持有，且不是卖出）
  22.       dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
  24.       //本日卖出 : (条件:昨天持有)
  25.       dp[i][1] = dp[i - 1][0] + prices[i];
  27.       // 不持有，但也不是卖出 : 1.昨天卖出，不持有  2.昨天没卖出，但也不持有
  28.       dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
  29.     }
  31.     // 最后一天还持有股票是没有意义的,肯定是不持有的收益高，不用对比 dp[len-1][0]
  32.     return Math.max(dp[len - 1][1], dp[len - 1][2]);
  33. }

股票交易 手续费

  1. 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
  2. 输出：8
  3. 解释：能够达到的最大利润:  
  4. 在此处买入 prices[0] = 1
  5. 在此处卖出 prices[3] = 8
  6. 在此处买入 prices[4] = 4
  7. 在此处卖出 prices[5] = 9
  8. 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

image.png

  1. // dp
  2. public int maxProfit(int[] prices, int fee) {
  3.     int len = prices.length;
  4.     int[][] dp = new int[len + 1][2];
  5.     dp[0][0] = 0;
  6.     dp[0][1] = - prices[0];
  8.     for (int i = 1; i < len; i++) {
  9.         dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
  10.         dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);
  11.     }
  13.     return sell;
  14. }
  15. // 空间压缩
  16. public int maxProfit(int[] prices, int fee) {
  17.     int len = prices.length;
  18.     int sell = 0;
  19.     int buy = - prices[0];
  21.     for (int i = 1; i < len; i++) {
  22.         sell = Math.max(sell, buy + prices[i] - fee);
  23.         buy = Math.max(sell - prices[i], buy);
  24.     }
  26.     return sell;
  27. }