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

题目：309. 买卖股票的最佳时机含冷冻期 ↗

状态机建模#

在 188.买卖股票的最佳时机 IV中，我们只有两个大类：买（持有）和卖（不持有）。

但在这一题中，由于冷冻期的存在，“不持有”被分成了两种完全不同的情况：

1. 状态 0：持有股票
2. 状态 1：刚刚卖出，处于冷冻期
   • 特点：这个状态是卖出动作激发的，下一天强制不能买。
3. 状态 2：不持有股票，且不在冷冻期
   • 特点：这个状态意味着你已经休息够了，随时可以买入。

状态转移方程#

设 $f[i][s]$ 为第 $i$ 天结束时，处于状态 $s$ 的最大利润。

状态 0：今天结束后我“手里有货”

• 昨天就有货，今天歇着：$f[i-1][0]$
• 昨天没货且不在冷冻期（状态 2），今天刚买入：$f[i-1][2] - price$
• 方程： $f[i][0] = \max(f[i-1][0], f[i-1][2] - price)$

状态 1：今天结束后我“刚刚卖出”

• 唯一来源：昨天我手里有货（状态 0），今天我把它卖了：$f[i-1][0] + price$
• 方程： $f[i][1] = f[i-1][0] + price$

状态 2：今天结束后我“两手空空且能买”

• 昨天就是这个状态，今天继续歇着：$f[i-1][2]$
• 昨天我是刚卖完的冷冻期（状态 1），今天冷冻期解除了：$f[i-1][1]$
• 方程： $f[i][2] = \max(f[i-1][2], f[i-1][1])$

Question：「刚刚卖出」和「处于冷冻期」不应该是两种状态吗？即昨天刚刚卖出，今天处于冷冻期

这里对状态的定义为：第 $i$ 天结束后所处的状态，而不是所谓的“第 $i$ 天所处的状态”。

代码实现#

我们可以发现，第 $i$ 天的状态只取决于第 $i - 1$ 天，因此可以直接用三个变量来维护。

public int maxProfit(int[] prices) {	
	int hold = -prices[0];  // 状态0
	int sold = 0;           // 状态1
	int rest = 0;           // 状态2

	for (int i = 1; i < prices.length; ++i) {
		int nextHold = Math.max(hold, rest - prices[i]);
		int nextSold = hold + prices[i];
		int nextRest = Math.max(rest, sold);

		hold = nextHold;
		sold = nextSold;
		rest = nextRest;
	}

	// 最大利润一定处于“手里没货”的状态
	return Math.max(sold, rest);
}