动态规划：买卖股票需要冷静期！

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

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

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

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

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

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

思路

相对于动态规划：122.买卖股票的最佳时机II，本题加上了一个冷冻期

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

那么本题则需要第三个状态：不持有股票（冷冻期）的最多现金。

动规五部曲，分析如下：

1. 确定dp数组以及下标的含义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

j的状态为：

• 0：持有股票后的最多现金
• 1：不持有股票（能购买）的最多现金
• 2：不持有股票（冷冻期）的最多现金

1. 确定递推公式

达到持有股票dp[1][0]状态，有两个具体操作：

• 操作一：前一天就是持有股票状态，dp[i][0] = dp[i - 1][0]
• 操作二：今天买入了，dp[i][0] = dp[i - 1][1] - prices[i]

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

达到不持有股票（能购买）的最多现金dp[i][1] 状态，有两个操作：

• 操作一：前一天卖出了股票在冷冻期，即:dp[i][1] = dp[i - 1][2]
• 操作二：前一天就是不持有股票（能购买）的状态，即：dp[i][1] = dp[i - 1][1]

dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);

达到不持有股票（冷冻期）的最多现金dp[i][2]状态，只有一个操作，即：前一天卖出股票

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

把这三种情况分析清楚了，这道题目就理解的差不多了。

1. dp数组如何初始化

持有股票，dp[0][0] = -prices[0]，买入股票所省现金为负数。

不持有股票（能购买）的最多现金dp[0][1] = 0，还没有买卖，现金为0

不持有股票（冷冻期）的最多现金dp[0][2]，这个状态其实是依赖前一个状态的买卖，但没有之前了。

那么来看看递推公式对dp[0][2]的要求。

从递推公式dp[i][2] = dp[i - 1][0] + prices[i];可以看出，dp[0][2]初始为任何数值都可以，反正dp[1][2] 要从新计算，不依赖dp[0][2]。

从递归公式dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]); 可以看出，dp[0][2]只要别大于0就行，因为dp[0][1]为0，而dp[1][1]取 dp[0][1]和dp[0][2]最大值，dp[1][1]本应该是0的（第二天不持有股票（能购买）的最多现金），如果dp[0][2]初始为大于0的数值，就影响了dp[1][1]。

所以理论上来说，dp[0][2]只要初始为小于等于0的任何一个数值都可以！

那么我们就统一都初始为0了。

代码如下：

vector<vector<int>> dp(n, vector<int>(3, 0));

初始化其实很有讲究，很多同学可能是稀里糊涂的全都初始化0，反正就可以通过，但没有想清楚，为什么都初始化为0。

如果大家仔细学习了「代码随想录」背包问题专题，就会发现初始化和遍历顺序，可以问出很多考察算法本质的问题。

1. 确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

1. 举例推导dp数组

以 [1,2,3,0,2] 为例，dp数组如下：

最后两个状态 不持有股票（能购买） 和 不持有股票（冷冻期）都有可能最后结果，取最大的。

以上五部分析完毕， C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(3, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];

        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

当然，空间复杂度可以优化，定义一个dp[2][3]大小的数组就可以了，就保存前一天的当前的状态，感兴趣的同学可以自己去写一写，思路是一样的。