动态规划_leetcode.309.最佳买卖股票时期含冷冻期

🌸题目

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

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

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

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

前言

对于力扣平台上的股票类型的题目：

121. 买卖股票的最佳时机

122. 买卖股票的最佳时机 II

123. 买卖股票的最佳时机 III

124. 买卖股票的最佳时机 IV

（本题）309. 最佳买卖股票时机含冷冻期

714. 买卖股票的最佳时机含手续费

剑指 Offer 63. 股票的最大利润

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

第 1 步：状态定义

dp [i] [j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时的最大收益。

这里 j 取三个值：

• 0 表示不持股且当天没卖出,定义其最大收益dp[i] [0]；
• 1 表示持股，定义其最大收益dp[i] [1]；
• 2 表示不持股且当天卖出了，定义其最大收益dp[i][2]。

第 2 步：状态转移方程

• 第i天不持股且没卖出的状态dp[i] [0]，也就是我没有股票，而且还不是因为我卖了它才没有的，那换句话说是从i-1天到第i天转移时，它压根就没给我股票！所以i-1天一定也是不持有，那就是不持有的两种可能：

  • i-1天不持股且当天没有卖出dp[i-1] [0]；
  • i-1天不持股但是当天卖出去了dp[i-1] [2]；

• 所以： dp[i] [0]=max(dp[i-1] [0],dp[i-1] [2])

• 第i天持股dp[i] [1]，今天我持股，来自两种可能：

  1、要么是昨天我就持股，今天继承昨天的，也就是dp[i-1] [1]，这种可能很好理解；

  2、要么是昨天我不持股，今天我买入的，但前提是昨天我一定没卖！因为如果昨天我卖了，那么今天我不能交易！也就是题目中所谓“冷冻期”的含义，只有昨天是“不持股且当天没卖出”这个状态，我今天才能买入！所以是dp[i-1] [0]-p[i]。所以： dp[i] [1]=max(dp[i-1] [1],dp[i-1] [0]-p[i])

• i天不持股且当天卖出了，这种就简单了，那就是说昨天我一定是持股的，要不然我今天拿什么卖啊，而持股只有一种状态，昨天持股的收益加上今天卖出得到的新收益，就是dp[i-1] [1]+p[i]啦

与之前股票问题的不同之处只在于：从不持股状态不能直接到持股状态，得经过一个冷冻期，才能到持股状态。

第 3 步：思考初始化

• 在第 0 天，不持股的初始化值为 0，
• 持股的初始化值为 -prices[0]（表示购买了一股），
• dp[0] [2]=0;//可以理解成第0天买入又卖出，那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0，所以初始化为0是合理

第 4 步：思考输出

最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可

参考代码：

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][2]);
		dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
		dp[i][2] = dp[i - 1][1] + prices[i];
	}
	
	return Math.max(dp[len - 1][0], dp[len - 1][2]);
}

第 5 步：思考空间优化

​ 由于当前天只参考了昨天的状态值，因此可以考虑使用「滚动数组」。

public int maxProfit1(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][2]);
		dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
		dp[i & 1][2] = dp[(i - 1) & 1][1] + prices[i];
	}
	
	return Math.max(dp[(len - 1) & 1][0], dp[(len - 1) & 1][2]);
}

由于状态值就 3 个，并且只关心最后 1 天的状态值，还可以使用滚动变量的方式把状态表格优化到一行。

public int maxProfit2(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, dp[2]);
		dp[1] = Math.max(preStock, preCash - prices[i]);
		dp[2] = preStock + prices[i];
		
        preCash = dp[0];
        preStock = dp[1];
	}
	
	return Math.max(dp[0], dp[2]);
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！