解题思路

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

第 1 步：状态定义

dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益。
这里 j 取三个值：

• 0 表示不持股；
• 1 表示持股；

• 2 表示处在冷冻期。

  第 2 步：状态转移方程

• 不持股可以由这两个状态转换而来：（1）昨天不持股，今天什么都不操作，仍然不持股。（2）昨天持股，今天卖了一股。

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

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

与之前股票问题的不同之处只在于：

从不持股状态不能直接到持股状态，得经过一个冷冻期，才能到持股状态。

第 3 步：思考初始化

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

第 4 步：思考输出

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

• Java

  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)O(N)，这里 NN 是股价数组的长度，只遍历了一次；

• 空间复杂度：O(N)O(N)。

  第 5 步：思考状态压缩

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

• Java

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

由于状态值就 3 个，还可以使用滚动变量的方式把状态压缩到一行。
参考代码 3：

• Java

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