力扣小白刷题之最佳买卖股票时机含冷冻期
题目描述
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
设计一个算法算出最大利润。在满足以下约束的条件下，你可以尽可能地完成更多的交易(多次买卖一只股票)：
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后，你无法在第二天买入股票(即冷冻期是1天)。
思路
参考自：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/fei-zhuang-tai-ji-de-dpjiang-jie-chao-ji-tong-su-y/
-
不要关注冷冻期，只关注卖出的那一天。
-
题目中定义的 冷冻期 = 卖出的那一天的后一天。题目设置冷冻期的意思是，如果昨天卖出了，今天不可买入，那么关键在于哪一天卖出，然后只要在今天想买入的时候判断一下前一天是不是刚刚卖出即可，所以关键的一天是卖出的那天，而不是卖出的后一天。
-
因为当天卖出的股票实际上也是属于“不持有”的状态，那么，第 i 天如果不持有，那这个“不持有”就有两种状态：
- 本来就不持有
- 第 i 天因为卖出了股票才变得不持有
-
而持有股票依旧只有一种状态。
-
所以对于每一天 i，都有可能是三种状态：
- 不持股且当天没卖出，定义其最大收益 dp[i][0]
- 持股，定义其最大收益 dp[i][1]
- 不持股且当天卖出了，定义其最大收益 dp[i][2]
-
初始化：
- dp[0][0] = 0; //本来就不持有，啥也没干
- dp[0][1] = -1 * prices[0]; //第 0 天只买入
- dp[0][2] = 0; // 可以理解为第 0 天买入又卖出，那么低 0 天就是“不持股且当天卖出”这个状态了，其收益为 0，所以初始化为 0.
-
思路分析：
-
第 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]，今天我持股，来自两种可能：
- 要么是昨天我就持股，今天继承昨天的，也就是dp[i - 1][1];
- 要么，是昨天我不持股，今天我买入的，但前提是昨天我一定没卖！因为如果我昨天卖了，那么今天我不能交易！也就是题目中“冷冻期”的含义，只有昨天是“不持股且当天没卖出”这个状态，我今天才能买入！所以是 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] (卖出所以 +)
所以，dp[i][2] = dp[i - 1][1] + p[i]
- 总结：最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可。
-