「力扣」第 309 题：最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
说明：
1、本文对状态的定义和状态转移可能有一些别扭。
2、我对冷冻期的处理是：只要不持股过了一天，就一直处于冷冻期，直到再购入股票为止。
3、如果对这一点理解上有困难的朋友，不是你们的问题哈。不用纠结我的做法，我认为只要是状态定义准确，状态转移方程正确即可，具体细节上不一定跟我一样，以能通过系统测评为准。
这道题增加了冷冻期这样一个条件，也没有限制多少笔交易。因此只需要增加一个状态（表示处在“冷冻期”）即可。
注意：这里是增加一个状态，不是增加一维状态。
第 1 步：状态定义
dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益。
这里 j 取三个值：
0表示不持股；1表示持股；2表示处在冷冻期。
第 2 步：状态转移方程
- 不持股可以由这两个状态转换而来：（1）昨天不持股，今天什么都不操作，仍然不持股。（2）昨天持股，今天卖了一股。
- 持股可以由这两个状态转换而来：（1）昨天持股，今天什么都不操作，仍然持股；（2）昨天处在冷冻期，今天买了一股；
- 处在冷冻期只可以由不持股转换而来，因为题目中说，刚刚把股票卖了，需要冷冻 1 天。
上面的分析可以用下面这张图表示：
{:width=500}{:align=center}
与之前股票问题的不同之处只在于：
从不持股状态不能直接到持股状态，得经过一个冷冻期，才能到持股状态。
第 3 步：思考初始化
在第 0 天，不持股的初始化值为 0，持股的初始化值为 -prices[0]（表示购买了一股），虽然不处于冷冻期，但是初始化的值可以为 0。
第 4 步：思考输出
每一天都由前面几天的状态转换而来，最优值在最后一天。取不持股和冷冻期的最大者。
参考代码 1：
public class Solution {
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][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i]);
dp[i][2] = dp[i - 1][0];
}
return Math.max(dp[len - 1][0], dp[len - 1][2]);
}
}复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是股价数组的长度，只遍历了一次；
- 空间复杂度：$O(N)$。
第 5 步：思考状态压缩
由于当前天只参考了昨天的状态值，因此可以考虑使用滚动数组。
参考代码 2：
public class Solution {
public int maxProfit(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][1] + prices[i]);
dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][2] - prices[i]);
dp[i & 1][2] = dp[(i - 1) & 1][0];
}
return Math.max(dp[(len - 1) & 1][0], dp[(len - 1) & 1][2]);
}
}复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是股价数组的长度，只遍历了一次；
- 空间复杂度：$O(1)$，状态数组里元素的个数是常数。
由于状态值就 3 个，还可以使用滚动变量的方式把状态压缩到一行。
参考代码 3：
public class Solution {
public int maxProfit(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, preStock + prices[i]);
dp[1] = Math.max(preStock, dp[2] - prices[i]);
dp[2] = preCash;
preCash= dp[0];
preStock = dp[1];
}
return Math.max(dp[0], dp[2]);
}
}复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是股价数组的长度，只遍历了一次；
- 空间复杂度：$O(1)$，状态数组里元素的个数是常数。
