题意

题目链接

计算最大利润（在约束条件下）：

  • 不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）
  • 卖出股票后，无法在第二天买入股票（冷冻期为一天）

方法

这道题是最近遇见最难处理的一道DP题。

我们可以试想对于每一天的i，都有可能是三种状态：

  1. 不持股且当天没有卖出$dp[i][0]$;
  2. 持股$dp[i][1]$;
  3. 不持股且当天卖了$dp[i][2]$;

初始化：

$dp[0][0]$ = 0;

$dp[0][1]$ = -prices[0];

$dp[0][2]$ = 0;

分析：

第i天不持股且没有卖出，所以有两种可能：

  1. i-1天不持股且当天没有卖出

  2. i-1天不持股但是当天卖出去了

    所以： $dp[i][0]=max(dp[i-1][0],dp[i-1][2])$

第i天持股，也有两种可能：

  1. 昨天持股，今天继承昨天的

  2. 昨天不持股，今天买入。这里的前提是昨天一定没有卖，如果卖了则今天就无法交易了

    所以：$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])$

第i天不持股且当天卖出了 == $dp[i][2]=dp[i-1][1]+p[i]$

最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if(n<=1) return 0;
        int [][] dp = new int[n][3];
        dp[0][0]=0;
        dp[0][1]=-1*prices[0];
        dp[0][2]=0;
        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
            dp[i][2] = dp[i-1][1]+prices[i];
        }
        return Math.max(dp[n-1][0],dp[n-1][2]);
    }
}