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

加入了冷冻期，让题目变得复杂起来了，但是思路还是差不多的，通过状态的转换来确定状态转移方程，初始化。

通过分析，化繁为简，可以发现加入了冷冻期后，今天一共有三种操作：1.持有股票dp[i][0]；2.无股票dp[i][1]；3.今天卖股票（第二天为冷冻期）dp[i][2]（前一天刚买过股票，此时手中没有股票）

持有股票可以由两种状态转换过来：昨天就持有股票dp[i - 1][0]。昨天没有股票（冷冻期不能购买股票），今天新买股票dp[i - 1][1] - prises[i]

无股票可以有两种状态转换过来：昨天就无股票dp[i - 1][1]。昨天卖了股票，今天为冷冻期dp[i - 1][2]

今天买股票只可以从一种状态转换过来：昨天持有股票，今天售卖dp[i - 1][0] + prices[i]

对于初始值的确定，第0天只可能买，因此将dp[0][0]初始化为-prices[0]即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(2, {0, 0, 0});
        dp[0][0] = -prices[0];
        for(int i = 1; i < prices.size(); i++)
        {
            dp[1][0] = max(dp[0][0], dp[0][1] - prices[i]);
            dp[1][1] = max(dp[0][2], dp[0][1]);
            dp[1][2] = dp[0][0] + prices[i];

            dp[0] = dp[1];
        }
        return max(dp[1][1], dp[1][2]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16