LeetCode309：最佳买卖股票时机含冷冻期

要求

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

卖出股票后的第 2 天为冷冻期。即：

• 卖出股票的当天：不持股；
• 卖出股票的第 2 天：冷冻期（不能买入股票，当然也不能卖出股票）；
• 卖出股票的第 3 天：可以买入股票，也可以什么都不操作。

方法：动态规划
1、状态定义：dp[i][j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时，我们手上拥有的金钱数。
这里的 j 可以取三个值：

• 0 表示：今天 不是 卖出了股票的不持股状态；
• 1 表示：持股；
• 2 表示：今天由于卖出了股票的不持股状态；

2、推导状态转移方程
0的转移：

• 昨天0，今天0 —> 可转移，今天什么都不做
• 昨天0，今天1 —>可转移，今天 买入股票

1的转移

• 昨天1，今天1 —>可转移，今天什么也不干
• 昨天1，今天2 —>可转移，卖出

2的转移

• 昨天2，今天0 —>可以转移，今天冷冻期

3、初始化：在第0天，不持股初始化0，持股初始化值为-prices[0]

4、输出：每一天的状态都是由前几天状态转换而来的，最优值在最后一天，取不持股和冷冻期的最大值

public class LeetCode309 {
    public int maxProfit(int[] prices) {
        if (prices.length < 2){
            return 0;
        }
        //dp[i][j]表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时的最大收益。
        int[][] dp = new int[prices.length][3];
        //定义第一天的初始值
        dp[0][0] = 0; //不持股 收益0
        dp[0][1] = -prices[0]; //持股 收益为第一天股价的负数
        dp[0][2] = 0; // 第一天不能是冷冻期 收益0

        for (int i = 1; i < prices.length; i++) {
            //第i天，不是由于卖出股票而不持股，持有现金；今天不操作||刚过冷冻期
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            //第i天，手上持有股票，现金；今天不操作||购买一股，扣除今天股价
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
            //第i天，由于卖出股票而不持股，冻结一天，收益为前一天现金 + 今天股价
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        //最后一天肯定不能持股，要提前卖掉，所以只需要比对空仓和冷冻期就行了。
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][2]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

---

方法二：优化递归
由于状态值就 3 个，并且只关心最后 1 天的状态值，还可以使用滚动变量的方式把状态表格优化到一行。不过为了使得状态转移正确进行，需要声明两个变量

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

    int[] dp = new int[3];
	//定义第一天的初始值
    dp[0] = 0; //不持股 收益0
    dp[1] = -prices[0]; //持股 收益为第一天股价的负数
    dp[2] = 0; // 第一天不能是冷冻期 收益0

    int pre0 = dp[0];
    int pre2 = dp[2];

    for (int i = 1; i < len; i++) {
     	//不持股最优对比：今天不操作（仍然不持股），冷冻期。
        dp[0] = Math.max(dp[0], pre2);
        //持股最优对比：今天不操作（仍然持股），今天买了一股，收益扣除今天股价。
        dp[1] = Math.max(dp[1], pre0 - prices[i]);
        //更新收益为持股时的现金 + 出售股价的最优收益。
        dp[2] = dp[1] + prices[i];
		
		//存储今日不持股两种情况的最佳收益，供明天比较
        pre0 = dp[0];
        pre2 = dp[2];
    }
    //最后一天肯定不能持股，要提前卖掉，只需要比对空仓和冷冻期就行了。
    return Math.max(dp[0], dp[2]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

---

我也是在慢慢学习的小白，不代表我的注释和你理解的一样，所以你可以有自己的理解，可以互相交流