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

Idea

对于第n天来说，我们有三种状态：

  • 手上有一只股票
  • 手上没有股票，并且不处于冷冻期
  • 手上没有股票，处于冷冻期

分别设这三种状态 第n天结束的时候的最大收益为f[n][0],f[n][1],f[n][2].

手上有一只股票

如果今天我们手上有一只股票，那么对于昨天来说 可能的操作有

  • 昨天手上也有一只股票 什么都没做
  • 昨天手上本来没有股票，买入了一只股票

由此 得到状态方程最佳买卖股票时机含冷冻期 - 图1

手上没有股票

如果今天我们手上没有股票 那么对于昨天来说 可能的操作：

  • 昨天手上也没有股票
  • 昨天处于冷冻期

由此 得到状态转移方程最佳买卖股票时机含冷冻期 - 图2

处于冷冻期

如果今天结束处于冷冻期 那么昨天

  • 昨天手上有股票 今天卖掉了

最佳买卖股票时机含冷冻期 - 图3

所以我们要求的就是手上没有股票 和处于冷冻期的第n天的最大值

Code

  1.      public static int maxProfit(int[] prices) {
  2.          int size=prices.length;
  3.          int[][] dp=new int[size][3];
  4.          dp[0][0]=-prices[0];
  5.          for(int i=1;i<size;i++)
  6.          {
  7.              dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
  8.              dp[i][1]=Math.max(dp[i-1][1], dp[i-1][2]);
  9.              dp[i][2]=dp[i-1][0]+prices[i];
  10.          }
  11.          return Math.max(dp[size-1][1], dp[size-1][2]);
  12.         }

三个状态 定义了三个数组来进行状态之间的转移