309_买卖股票的最佳时机含冷冻期.md

题目

309. 买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

输入: prices = [1]
输出: 0

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][]dp=new int[n+1][5];
        // dp[i][j]表示当前剩余的最大现金
        // j表示 第i天的状态, 
        // 0 表示持有股票
        // 1 表示保持卖出状态(不持有股票, 在之前就已经卖过了)
        // 2 表示当天卖出股票
        // 3 表示 冷冻期(只有一天)
        // 冷冻期的前一天只能是 [当天卖出股票]
        dp[0][0]=-prices[0]; 
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(Math.max(dp[i-1][0],dp[i-1][1]-prices[i])
                ,dp[i-1][3]-prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return Math.max(Math.max(dp[n-1][1],dp[n-1][2]),dp[n-1][3]);
    }
}

思路

有关于买卖股票的题目 , 一般我们都采用DP的做法。

本题的关键在于如何来确定 每一天 可能会存在的状态

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

首先最基本的我们可以通过题目确定两种状态 对于 i 天

1. 持有股票
2. 不持有股票

其次是关于冷冻期

1. 当天是冷冻期

也有可能当天我们进行的操作

1. 当天卖出
2. 当天购买

其中 当天购买可以归类为 持有股票 , 但是对于 当天卖出 需要特别作为一种状态(因为存在冷冻期)

那么我们定义DP 数组如下

定义dp[i][j] , 其中

j表示 第i天的状态,

• 0 表示持有股票
• 1 表示保持卖出状态(不持有股票, 在之前就已经卖过了)
• 2 表示当天卖出股票
• 3 表示 冷冻期(只有一天)

---

接下来讨论如何进行状态转移

对于 dp[i][0] , 能转移成此状态的前置状态可能为

• dp[i-1][0] : 第i天我们什么也不做
• dp[i-1][1] - prices[i]: 第i天我们购入股票
• dp[i-1][3] - prices[i] : i-1天是冷冻期, 我们在第i天购入股票

以上三种我们取最大值即可

对于dp[i][1] 有 dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);

• 可能保持之前的卖出状态 or 在 i-1天卖出

最后的两种状态:

• dp[i][2]=dp[i-1][0]+prices[i]; : 前一天持有股票, 今天卖出
• dp[i][3]=dp[i-1][2]; : 前一天卖出 , 今天就是冷冻期

---

如何初始化:

对于状态的含义 , 首先可以初始化dp[0][0]=-prices[i]

对于 状态2 3 在第一天无法达到 , 因此 初始化为0

需要注意的是状态1 , 我们可以参考状态转移的方程 , 对于第二天 , 保持卖出状态要求前一天之前已经卖出, 而不是前一天卖出, 因此 初始化dp[0][1]=0

---

最后返回结果 在 完成交易的几种状态中取最大值返回即可

return Math.max(Math.max(dp[n-1][1],dp[n-1][2]),dp[n-1][3]);