【leetcode】309. 最佳买卖股票时机含冷冻期

题目内容

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

思路分析

本题也是股票系列的一道题目。题目中提到：

对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

看到状态这个词就很明显的想到动态规划了（外加股票系列本来就动态规划用的多），虽然最后用的状态不是这个...

本题是自己定了状态仔细推导以后发现不对劲，又改变方向定出来了正确的状态，最后在没看答案的情况下做出来了，还是很有成就感的😁

（想写一开始的错误思路来着发现忘了，只好略过）

方法一：动态规划

首先分析题目，每天有四种动作：非冷冻期不动，冷冻期不动，买入，卖出；有两种状态：持仓，空仓；其中空仓又可分为刚卖完（第二天冷冻），以及空仓但第二天不冷冻。

因此，设cash[i][j]代表第i天状态j下的最大现金，设遍历时，第i天为“今天”，则j的含义为今天交易完成后：

0：今天空仓明天冷冻
1：今天空仓明天不冷冻
2：今天持仓

状态转移关系及其方程如下：

// 昨天持仓今天卖 -> 空仓第二天冷冻
cash[i][0] = cash[i - 1][2] + prices[i];
// 昨天【空仓第二天冷冻】今天不动 / 昨天【空仓第二天不冷冻】今天不动
// -> 空仓第二天不冷冻
cash[i][1] = max(cash[i - 1][0], cash[i - 1][1]);
// 昨天持仓今天不动 / 昨天【持仓第二天不冷冻】今天买 -> 今天持仓
cash[i][2] = max(cash[i - 1][2], cash[i - 1][1] - prices[i]);

边界条件为：

cash[0][0] = 0;
cash[0][1] = 0;  // 不买则空仓第二天不冷冻
cash[0][2] = -prices[0];  // 买则持仓

其中，cash[0][0]的初始值为0是因为今天的状态0仅决定明天的状态1，且第二天的状态1是前一天的状态0和状态1共同决定的。而第一天的状态0可以理解为当日买入当日卖出，没有收益且只有弊端，因此初始值小于等于0时对答案都没有影响。（感觉自己不是很明白所以讲不清楚...参考链接的下方评论区有）

最后，返回最后一天的三种状态中的最大现金即可max(cash[最后一天][0],cash[最后一天][1],cash[最后一天][2])。

方法二：动态规划优化

有两个优化点：

和之前的股票题目一样，每天的状态只和前一天的状态有关，因此只需要写三个变量记录前一天的状态，而不需要使用大小为O(n)的数组
最后一天持有股票没有意义，手上的现金不能达到最多，因此只需要返回max(cash[最后一天][0],cash[最后一天][1])

代码

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    // 动态规划
    // 时间复杂度O(n)，空间复杂度O(n)
    int maxProfit1(vector<int>& prices) {
        int n = prices.size();

        if (n <= 1) return 0;

        // cash：当前状态下的最大现金
        // 0 - 空仓第二天冷冻
        // 1 - 空仓第二天不冷冻
        // 2 - 持仓
        vector<vector<int>> cash(n, vector<int>(3));

        cash[0][2] = -prices[0];

        // 设第i天是“今天”
        for (int i = 1; i < n; ++i) {
            // 昨天持仓今天卖 -> 空仓第二天冷冻
            cash[i][0] = cash[i - 1][2] + prices[i];
            // 昨天【空仓第二天冷冻】今天不动 / 昨天【空仓第二天不冷冻】今天不动
            // -> 空仓第二天不冷冻
            cash[i][1] = max(cash[i - 1][0], cash[i - 1][1]);
            // 昨天持仓今天不动 / 昨天【持仓第二天不冷冻】今天买
            cash[i][2] = max(cash[i - 1][2], cash[i - 1][1] - prices[i]);

            cout << cash[i][0] << " " << cash[i][1] << " " << cash[i][2] << endl;
        }

        // 最后返回现金的最大值
        return max(max(cash[n - 1][0], cash[n - 1][1]), cash[n - 1][2]);
    }

    // 动态规划优化
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit(vector<int> & prices) {
        int n = prices.size();

        if (n <= 1) return 0;

        // cash：当前状态下的最大现金
        // 0 - 空仓第二天冷冻
        // 1 - 空仓第二天不冷冻
        // 2 - 持仓
        // vector<vector<int>> cash(n, vector<int>(3));
        int pre_empty_freeze{ 0 }, pre_empty_not_freeze{ 0 }, pre_hold{ -prices[0] },
            empty_freeze{ 0 }, empty_not_freeze{ 0 }, hold{ 0 };

        // 设第i天是“今天”
        for (int i = 1; i < n; ++i) {
            // 昨天持仓今天卖 -> 空仓第二天冷冻
            empty_freeze = pre_hold + prices[i];
            // 昨天【空仓第二天冷冻】今天不动 / 昨天【空仓第二天不冷冻】今天不动
            // -> 空仓第二天不冷冻
            empty_not_freeze = max(pre_empty_freeze, pre_empty_not_freeze);
            // 昨天持仓今天不动 / 昨天【持仓第二天不冷冻】今天买
            hold = max(pre_hold, pre_empty_not_freeze - prices[i]);

            pre_empty_freeze = empty_freeze;
            pre_empty_not_freeze = empty_not_freeze;
            pre_hold = hold;
        }

        // 最后返回现金的最大值
        //return max(max(empty_freeze, empty_not_freeze), hold);
        // 最后一天持有股票没有意义
        return max(empty_freeze, empty_not_freeze);
    }
};

int main() {
    Solution s;
    vector<int> input{ 1,2,3,0,2 };

    int output;
    output = s.maxProfit(input);

    return output;
}

收获

练习了动态规划，自己完整的写出了答案。
打印动态规划的状态数组然后看哪里与自己预期的不符，可以便于调试