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

不限交易次数

动态规划-数组递推

类似123和188，冷冻期决定了第 i 天持有股票的最大利润依赖于前一天持有或前两天不持有今天买入后的利润。 因为今天要依赖前一天或前两天，所以base case有两个，一个是第一天，一个是第二天。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;  // 获取价格数组的长度
        // 定义动态规划数组，dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润
        int[][] dp = new int[n][2];
        
        for (int i = 0; i < n; i++) {
            // base case 1
            // 当 i 为 0 (即第0天) 时的处理
            if (i == 0) {
                dp[i][0] = 0;  // 第0天不持有股票的利润为0
                dp[i][1] = -prices[i];  // 第0天持有股票的利润为 -prices[i]
                continue;
            }
            // base case 2
            // 当 i 为 1 (即第1天) 时的处理
            if (i == 1) {
                // 第1天不持有股票的最大利润为前一天不持有股票的利润或前一天持有后今天卖出
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 第1天持有股票的最大利润为前一天持有股票的利润或前一天不持有今天买入
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
                //   dp[i][1]
                // = max(dp[i-1][1], dp[-1][0] - prices[i])
                // = max(dp[i-1][1], 0 - prices[i])
                // = max(dp[i-1][1], -prices[i])
                continue;
            }
            
            // 通常情况下的状态转移方程
            // 第 i 天不持有股票的最大利润：保持前一天的不持有状态或者前一天持有今天卖出
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第 i 天持有股票的最大利润：保持前一天的持有状态或者前两天不持有今天买入（卖出后需要冷却一天）。
            // 严格来说是max(dp[i-1][1], dp[i-2][0]-prices[i], -prices[i])，
            // 其中-prices[i]指前1天没有股票今天再买，不是前2天卖了股票今天再买！那是第二项的意思。
            // 但是dp[i-2][0]一定大于0，所以把第三项略去了。前两天不持有可能是前两天持有然后卖了，也可能是前两天根本就没有。重点。
            // 由于 i - 2 也可能小于 0，所以上面多了一个 i - 2 < 0 的 base case
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }
        
        return dp[n - 1][0];  // 返回最后一天不持有股票的最大利润
    }
}

时间复杂度O(N)，空间复杂度O(N)

动态规划-数组递推-滚动更新

第一天不持有股票的最大利润dp_i_0，第一天持有股票的最大利润dp_i_1，前两天不持有股票的最大利润dp_pre_0。临时变量tmp存储前一天不持有股票的最大利润，滚动更新dp_i_0和dp_i_1，更新 dp_pre_0 为tmp。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        // 初始化滚动变量
        int noStockToday = 0;  // 表示今天不持有股票的最大利润
        int holdStockToday = -prices[0];  // 表示今天持有股票的最大利润
        int noStockTwoDaysAgo = 0;  // 表示两天前不持有股票的最大利润。重点。

        // for循环先暂存，再操作，再更新数据。
        for (int i = 1; i < n; i++) {
            // 暂存今天不持有股票的利润，用于更新两天前的状态
            // 更新前的noStockToday是昨天的状态，更新后的noStockToday是今天的状态。
            int noStockYesterday = noStockToday;

            // 更新今天不持有股票的最大利润：
            // 1. 继续昨天不持有股票的状态
            // 2. 或者昨天持有股票，今天卖出
            noStockToday = Math.max(noStockToday, holdStockToday + prices[i]);
            // 更新今天持有股票的最大利润：
            // 1. 继续昨天持有股票的状态
            // 2. 或者两天前不持有股票，今天买入
            holdStockToday = Math.max(holdStockToday, noStockTwoDaysAgo - prices[i]);

            // 更新两天前不持有股票的最大利润。明天会用昨天的数据。
            // 注意一定要先用noStockTwoDaysAgo，再更新noStocksTwoDaysAgo。
            noStockTwoDaysAgo = noStockYesterday;
        }

        // 返回最后一天不持有股票的最大利润
        return noStockToday;
    }
}

时间复杂度O(N)，空间复杂度O(1)