本文主要是介绍「动态规划」买卖股票的最佳时机，如何处理冷冻期？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
309. 买卖股票的最佳时机含冷冻期
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
给定一个整数数组prices，其中prices[i]表示第i天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）：卖出股票后，你无法在第二天买入股票 （即冷冻期为1天）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 输入：prices = [1,2,3,0,2]，输出：3，解释：对应的交易状态为：买入，卖出，冷冻期，买入，卖出。
- 输入：prices = [1]，输出：0。
提示：1 <= prices.length <= 5000，0 <= prices[i] <= 1000。
我们用动态规划的思想来解决这个问题。
确定状态表示：根据经验和题目要求，我们用dp[i]表示：在第i天结束后的最大利润。但是，这个状态表示不够细致，不容易推出状态转移方程。
在第i天结束后：
- 如果你手里有股票，那么你处于买入状态。
- 如果你手里没有股票，且在第i天刚刚卖出股票，那么你处于冷冻期状态。
- 如果你手里没有股票，且并没有在第i天卖出股票，那么你处于可交易状态。
所以，我们把状态表示细分为：
- 用dp[i][0]表示：在第i天结束后，处于买入状态下，此时的最大利润。
- 用dp[i][1]表示：在第i天结束后，处于冷冻期状态下，此时的最大利润。
- 用dp[i][2]表示：在第i天结束后，处于可交易状态下，此时的最大利润。
推导状态转移方程：我们思考一下在第i天可以进行的操作。
- 在第i - 1天结束后，如果你处于买入状态：
- 你可以在第i天什么都不做，继续持有股票，在第i天结束后依然处于买入状态。
- 你也可以在第i天卖出股票，在第i天结束后处于冷冻期状态。
- 在第i - 1天结束后，如果你处于冷冻期状态：
- 你只能选择什么都不做，在第i天结束后就解冻了，处于可交易状态。
- 在第i - 1天结束后，如果你处于可交易状态：
- 你可以选择在第i天什么都不做，在第i天结束后依然处于可交易状态。
- 你也可以选择在第i天买入股票，在第i天结束后处于买入状态。
- 你也可以选择在第i天买入股票，接着立刻卖出股票，在第i天结束后处于冷冻期状态。但是这么做是没意义的，并不会增加利润，所以在分析状态转移方程时不考虑这种操作。
如何计算利润呢？初始利润是0，
- 如果买入股票，那么利润要减去股票当天的价格。
- 如果卖出股票，那么利润就要加上股票当天的价格。
- 如果什么都不做，那么利润不变。
接下来，考虑最近的一步，即第i - 1天结束后的状态和第i天的操作。
- 如果第i天结束后处于买入状态，此时的最大利润dp[i][0]是以下情况的最大值。
- 如果第i - 1天结束后处于买入状态，在第i天什么都不做，在第i天结束后的最大利润就是在第i - 1天结束后的最大利润，即dp[i - 1][0]。
- 如果第i - 1天结束后处于可交易状态，在第i天买入股票，在第i天结束后的最大利润就是在第i - 1天结束后的最大利润减去股票在第i天的价格，即dp[i - 1][2] - prices[i]。
- 如果第i天结束后处于冷冻期状态，此时的最大利润dp[i][1]是以下情况的最大值。
- 由于不考虑买入后立刻卖出的情况，只有可能是在第i - 1天结束后处于买入状态，在第i天卖出股票，在第i天结束后的最大利润就是在第i - 1天结束后的最大利润加上股票在第i天的价格，即dp[i - 1][0] + prices[i]。
- 如果第i天结束后处于可交易状态，此时的最大利润dp[i][2]是以下情况的最大值。
- 如果第i - 1天结束后处于冷冻期状态，在第i天什么都不做，在第i天结束后的最大利润就是在第i - 1天结束后的最大利润，即dp[i - 1][1]。
- 如果第i - 1天结束后处于可交易状态，在第i天什么都不做，在第i天结束后的最大利润就是在第i - 1天结束后的最大利润，即dp[i - 1][2]。
综上所述：dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])，dp[i][1] = dp[i - 1][0] + prices[i]，dp[i][2] = max(dp[i - 1][1], dp[i - 1][2])。
初始化：根据状态转移方程，在计算dp[0][j]，其中j的范围是[0, 2]时，会越界访问，所以需要对其初始化。
- 如果第0天结束后处于买入状态，只能在第0天买入股票，显然dp[0][0] = -prices[0]。
- 如果在第0天结束后处于冷冻期状态，只能在第0天买入后立刻卖出股票（这种操作没有意义，但是初始化时只能这么解释），显然dp[0][1] = 0。
- 如果在第0天结束后处于可交易状态，只能在第0天什么都不做，显然dp[0][2] = 0。
综上所述：dp[0][0] = -prices[0]，dp[0][1] = dp[0][2] = 0。
填表顺序：根据状态转移方程，dp[i][j]依赖于dp[i - 1][j]，所以应沿着i增大的方向填表。
返回值：假设总共有n天，那么对于第i天，i的范围就是[0, n - 1]。如果要获取最大利润，那么第n - 1天结束后不能处于买入状态（手中有股票的话，在最后一天卖出会获得更高的利润），所以在第n - 1天结束后只有可能处于冷冻期状态或者可交易状态。再根据状态表示，我们最终要返回的是，在第n - 1天结束后处于冷冻期状态或者可交易状态这2种情况中，最大利润的较大值，即max(dp[n - 1][1], dp[n - 1][2])。
细节问题：由于下标i的范围是[0, n - 1]，下标j的范围是[0, 2]，所以dp表的规模是n x 3。
时间复杂度：O(N)，空间复杂度：O(N)。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// 创建dp表vector<vector<int>> dp(n, vector<int>(3));// 初始化dp[0][0] = -prices[0];// 填表for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);dp[i][1] = dp[i - 1][0] + prices[i];dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);}// 返回结果return max(dp[n - 1][1], dp[n - 1][2]);}
};这篇关于「动态规划」买卖股票的最佳时机，如何处理冷冻期？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
