力扣309-买卖股票的最佳时机含冷冻期（Java详细题解）

题目链接：309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

前情提要：

本题是由122. 买卖股票的最佳时机 II - 力扣（LeetCode）变形而来，122是可以买卖多次股票没有冷冻期，该题还添加了冷冻期这一个限定，我相信当你做完这道题或者看完我上道题的题解力扣122.-买卖股票的最佳时机 II（Java详细题解）-CSDN博客，写这道题会轻松一点。

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

本题相较于122. 买卖股票的最佳时机 II还难了不少，因为加上了冷冻期这一个限定，导致他的状态变多了。

在力扣122.-买卖股票的最佳时机 II中有两个状态，持有股票后的最多现金，和不持有股票的最多现金。

本题因为当卖出一次股票时就会陷入一天的冷冻期，所以我们肯定需要卖出股票的这个状态，因为只有确定这个状态，才能确定我们的冷冻期的状态。

那么我们不持股的状态就要做一个状态分离，分为一个卖出股票的最大现金和维持卖出股票状态的最大现金。

话不多说，我们用dp五部曲来系统分析一下。

1.确定dp数组和i下标的含义。

dp[i] [0]代表持股的最多现金。

dp[i] [1]代表维持卖出股票的最多现金。

dp[i] [2]代表卖出股票的最多现金。

dp[i] [3]代表冷冻期是的最多现金。

2.确定递推公式。

每个状态可以由哪些推出呢？

dp[i] [0] 可能之前就维持股票的最多现金，也可能当时就买入股票。

其中买入股票继续分为俩种，一种为前一天是冷冻期然后买入。

另一种是前一天是维持卖出股票的状态然后买入。

所以dp[i] [0] = Math.max(dp[i - 1] [0],Math.max(dp[i - 1] [3] - prices[i],dp[i - 1] [2] - prices[i]));

dp[i] [1]可能之前也是维持卖出股票的最多现金，也可以是冷冻期后卖出股票的最多现金.

为什么不考虑卖出股票后的最多现金呢？因为卖出现金后就会陷入冷冻期，所以卖出股票后面的状态只能是冷冻期。

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

dp[i] [2] 只能在持股的状态后卖出股票所以 dp[i] [2] = dp[i - 1] [0] + prices[i]；

dp[i] [3]冷冻期也只有卖出股票后面是冷冻期所以 dp[i] [3] = dp[i - 1] [2]；

3.dp初始化。

由递推公式可以看出dp[i]由dp[i - 1]推出，所以递推的起点是在dp[0]。

dp[0] [0]下标为0天持股的最多现金就是买入当天的股票。

dp[0] [0] = -prices[0]；

dp[0] [1]代表维持卖出股票的最多现金。

dp[0] [2]代表卖出股票的最多现金。

dp[0] [3]代表冷冻期是的最多现金。

保持卖出股票状态（状态二），这里其实从「状态二」的定义来说，很难明确应该初始多少，这种情况我们就看递推公式需要我们给他初始成什么数值。

如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1] [1] - prices[i] ，即 dp[0] [1] - prices[1]，那么大家感受一下 dp[0] [1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后手里还剩的现金数量是不是就不对了。

今天卖出了股票（状态三），同上分析，dp[0] [2]初始化为0，dp[0] [3]也初始为0。

4.确定dp的遍历顺序。

由递推公式可以看出dp[i]由dp[i - 1]推出，所以dp的遍历顺序是从前往后推，所以dp从前往后遍历。

5.如果没有ac打印dp数组利于debug。

在这里插入图片描述

那么取结果的地方在你呢？其实状态2，3，4都有可能，所以我们要对这几个状态取一个最大值。

最终代码：

java">class Solution {
    public int maxProfit(int[] prices) {
        //我们怎么知道这个冷冻期在什么时候呢？ 其实只要找出卖出股票的时候就能找出冷冻期了
        //所以将不持有股票的的状态分为 保持卖出股票的状态 和卖出股票的状态
        //定义dp数组
        int [][] dp = new int [prices.length + 1][4];
        //初始化
        dp[0][0] = -prices[0];
        //dp遍历顺序
        for(int i = 1;i < prices.length; i++){
            dp[i][0] = Math.max(dp[i - 1][0],Math.max(dp[i - 1][3] - prices[i],dp[i - 1][1] - 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(dp[prices.length - 1][1],Math.max(dp[prices.length - 1][2],dp[prices.length - 1][3]));

    }
}