[数据结构与算法]LeetCode动态规划专题：第八天

最佳买卖股票含冷冻期

class Solution {
public:
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
    int maxProfit(vector<int>& prices) {
        if (prices.empty()){
            return 0;
        }
        int n = prices.size();
        int f0 = -prices[0], f1 = 0, f2 = 0;
        for (int i = 1; i < n; i ++ ){
            int g0 = max(f0, f2 - prices[i]);
            int g1 = f0 + prices[i];
            int g2 = max(f1, f2);
            f0 = g0;
            f1 = g1;
            f2 = g2;
        }
        return max(f1, f2);
    }
};

买卖股票的最佳时机含手续费

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int f0 = -prices[0];
        int f1 = 0;

        for (int i = 1; i < n; i ++ ){
            int g0 = max(f0, f1 - prices[i]);
            int g1 = max(f1, f0 + prices[i] - fee);
            f0 = g0;
            f1 = g1;
        }
        return f1;
    }
};