【leetcode】309.最佳买卖股票时机含冷冻期 （动态规划详细解析）

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

难度中等

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

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

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

示例:

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

说明：

• 这篇题解对状态的定义和状态转移可能有一些别扭；
• 我定义下的冷冻期只能从昨天不持股转化而来；
• 如果觉得不好理解的朋友，可以看看题解的评论区，不要纠结我的定义和状态转移的推导（这里含有一些主观的因素），只要是状态定义准确（全程保持一致），状态转移方程正确即可，具体的细节和理解上不一定跟我一样，以能通过系统测评为准。

补充：

• 解决股票系列问题，需要用到「动态规划」的无后效性这个概念，简单来说就是状态定义越具体，状态转移方程就越好得到。但是有的时候也不是越具体越好的，需要根据具体问题具体分析；
• 股票系列问题还可以借助「状态机」这个概念来完成，据说是更简单的，大家可以在股票系列问题的题解区和评论区找到相关知识的介绍。

这道题增加了冷冻期这样一个条件，也没有限制多少笔交易。因此只需要增加一个状态（表示当前这一天处在「冷冻期」）即可。注意：这里是增加一个状态，不是增加一维状态。

第一步：状态定义

dp[i][j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时的最大收益。

这里 j 取三个值：

• 0 表示不持股；
• 1 表示持股；
• 2 表示处在冷冻期。

第二步：状态转移方程

• 不持股可以由这两个状态转换而来：
  • 昨天不持股，今天什么都不操作，仍然不持股；
  • 昨天持股，今天卖了一股。
• 持股可以由这两个状态转换而来：
  • 昨天持股，今天什么都不操作，仍然持股；
  • 昨天处在冷冻期，今天买了一股；
• 处在冷冻期只可以由不持股转换而来，因为题目中说，刚刚把股票卖了，需要冷冻 1 天。

上面的分析可以用下面这张图表示：

与之前股票问题的不同之处只在于：从不持股状态不能直接到持股状态，得经过一个冷冻期，才能到持股状态。

第三步：思考初始化

在第 0 天，不持股的初始化值为 0，持股的初始化值为 -prices[0]（表示购买了一股），虽然不处于冷冻期，但是初始化的值可以为 0。

第四步：思考输出

每一天都由前面几天的状态转换而来，最优值在最后一天。取不持股和冷冻期的最大者。

参考代码 1：

• Java

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }

        int[][] dp = new int[len][3];

        // 初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i]);
            dp[i][2] = dp[i - 1][0];
        }
        return Math.max(dp[len - 1][0], dp[len - 1][2]);
    }
}

复杂度分析：

• 时间复杂度：O(N)，这里 N 是股价数组的长度，只遍历了一次；
• 空间复杂度：O(N)。

第五步：思考空间优化

由于当前天只参考了昨天的状态值，因此可以考虑使用「滚动数组」。

参考代码 2：

• Java

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }

        int[][] dp = new int[2][3];

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

        for (int i = 1; i < len; i++) {
            dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
            dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][2] - prices[i]);
            dp[i & 1][2] = dp[(i - 1) & 1][0];
        }
        return Math.max(dp[(len - 1) & 1][0], dp[(len - 1) & 1][2]);
    }
}

复杂度分析：

• 时间复杂度：O(N)，这里 NN 是股价数组的长度，只遍历了一次；
• 空间复杂度：O(1)，状态数组里元素的个数是常数。

由于状态值就 3 个，并且只关心最后 1 天的状态值，还可以使用滚动变量的方式把状态表格优化到一行。

参考代码 3：

• Java

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }

        int[] dp = new int[3];

        // 初始化
        dp[0] = 0;
        dp[1] = -prices[0];
        dp[2] = 0;

        int preCash = dp[0];
        int preStock = dp[1];

        for (int i = 1; i < len; i++) {
            dp[0] = Math.max(preCash, preStock + prices[i]);
            dp[1] = Math.max(preStock, dp[2] - prices[i]);
            dp[2] = preCash;

            preCash= dp[0];
            preStock = dp[1];
        }
        return Math.max(dp[0], dp[2]);
    }
}

复杂度分析：

• 时间复杂度：O(N)，这里 NN 是股价数组的长度，只遍历了一次；
• 空间复杂度：O(1)，状态数组里元素的个数是常数。