【动态规划】No 309. 最佳买卖股票时机含冷冻期

【动态规划】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

两状态解法

​ 思路：加了冰冻期后，对于当前没有股票的状态是没有影响的，仍是由昨天持有股票今天卖出、昨天不持有股票两种状态转化而来：

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

​ 而对于当前持有股票却不能直接使用昨天不持有股票的状态然后今天购买了，因为有可能昨天卖出了股票导致今天不能购买，所以这部分代码为：

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

​ 看到这可能会有疑问，这个只是包含前天没有股票的状态，如果昨天没有交易而且也没有股票岂不是没有统计？我们只是不需要昨天交易导致没有股票这一个状态而已。这是由于昨天没有交易而且也没有股票这一状态一定是由前天没有股票转移过来的，因为昨天有交易的话，前天是一定有股票的。

class Solution {
    public int maxProfit(int[] prices) {
        var len = prices.length;
        var dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(var i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i-1][1] + prices[i], dp[i-1][0]);
            if(i > 1) {
                dp[i][1] = Math.max(dp[i-2][0] - prices[i], dp[i-1][1]);
            } else {
                dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);
            }
        }

        return dp[len-1][0];
    }
}

四状态解法

​ 整个过程可以分为四个状态：

• 状态一：持有股票的状态，今天买入股票 或 之前就买入了股票但是一直没有卖出
• 状态二：不持有股票的状态，且保持卖出股票的状态，即两天前就卖出了股票一直没有操作
• 状态三：不持有股票的状态，且是今天卖出的股票
• 状态四：不持有股票的状态，冰冻期，即一天前卖出了股票

​ 则递推可以写为：

			// 持有股票的状态，由状态1、3转化而来，2状态今天是冰封期
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][3]) - prices[i]);
            // 不持有，且是两天前卖的，由更多天前卖的和3状态转化而来，2状态今天也是冰封期
            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];

​ 代码为：

class Solution {
    public int maxProfit(int[] prices) {
        var len = prices.length;
        var dp = new int[len][4];
        dp[0][0] = -prices[0];
        for(var i = 1; i < len; i++) {
            // 持有股票的状态
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][3]) - 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(Math.max(dp[len-1][1], dp[len-1][2]), dp[len-1][3]);
    }
}

一维数组优化

​ 思路是不变的，只是注意下面的定义和赋值的顺序，否则容易被覆盖修改

class Solution {
    public int maxProfit(int[] prices) {
        var len = prices.length;
        var dp = new int[4];
        dp[0] = -prices[0];

        for(var i = 1; i < len; i++) {
            // 持有状态
            dp[0] = Math.max(dp[0], Math.max(dp[1], dp[2]) - prices[i]);
            // 不持有状态，且是两天前卖的
            dp[1] = Math.max(dp[1], dp[2]);
            // 不持有状态，且是一天前卖的
            dp[2] = dp[3];
            // 不持有状态，且是当天卖的
            dp[3] = dp[0] + prices[i];
        }

        // System.out.println(Arrays.toString(dp));

        return Math.max(Math.max(dp[1], dp[2]), dp[3]);
    }
}