【刷题】动态规划——状态机模型：买卖股票时机含冷冻期（LeetCode 309）

题目链接

和买卖股票的时机 IV不同的是，这边不再限制k，但除了有货和无货外还多了一个冷冻期的状态。

用0表示有货，1表示无货，2表示冷冻期。
f[i, 0], f[i, 1], f[i, 2]分别表示经过i天，且第i天处于有货、无货、冷冻期状态。

一开始手中是无货的，所以入口在无货状态。
因为手中有货必然是花钱买的，不卖出只会比卖出亏，所以出口只有无货和冷冻期。
换成初始化就是f[0][0] = 0
根据状态机可以写出以下递推式。
f[i, 0] = max(f[i-1, 2], f[i-1, 0])
f[i, 1] = max(f[i-1, 0] - p, f[i-1, 1])
f[i, 2] = f[i-1, 1] + p

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size(), ans = 0;
        vector> f(n + 1, vector(3, -0x3f3f3f3f));
        f[0][0] = 0;
        for (int i = 1; i <= n; i ++) {
            int p = prices[i - 1];
            f[i][0] = max(f[i - 1][2], f[i - 1][0]);
            f[i][1] = max(f[i - 1][0] - p, f[i - 1][1]);
            f[i][2] = f[i - 1][1] + p;
            ans = max(ans, max(f[i][0], f[i][2]));
        }
        return ans;
    }
};

滚动数组优化

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size(), ans = 0;
        int f[3], g[3];
        g[0] = 0;
        g[1] = g[2] = -0x3f3f3f3f;
        for (int i = 1; i <= n; i ++) {
            int p = prices[i - 1];
            f[0] = max(g[2], g[0]);
            f[1] = max(g[0] - p, g[1]);
            f[2] = g[1] + p;
            ans = max(ans, max(f[0], f[2]));
            memcpy(g, f, sizeof(f));
        }
        return ans;
    }
};