搜索
您的当前位置:首页正文

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

来源:独旅网

和不同的是,这边不再限制k,但除了有货和无货外还多了一个冷冻期的状态。

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

一开始手中是无货的,所以入口在无货状态。
因为手中有货必然是花钱买的,不卖出只会比卖出亏,所以出口只有无货和冷冻期。
换成初始化就是f[0][0] = 0

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size(), ans = 0;
        vector<vector<int>> f(n + 1, vector<int>(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<int>& 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;
    }
};

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top