贪心

贪心的思想 看官解 当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。

评论区的解释很具体形象 假卖是最精妙的地方

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 1) return 0;
        int profit = 0;
        int cost = prices[0] + fee;
        for (int i = 1; i < n; i ++ ) {
            if (prices[i] + fee < cost) {
                cost = prices[i] + fee;
            }
            else if (prices[i] - cost > 0) {
                profit += prices[i] - cost;
                cost = prices[i]; // 最需要理解的地方
            }
        }
        return profit;
    }
};

动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        // 买入为负收益，而卖出为正收益
        // dp[?][0] dp[?][1]， 0 表示没有股票，1 表示持有股票
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i ++) {
            // 第i天不持有股票，前一天没有股票或者前一天出售了股票并支付手续费
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            // 第i天持有股票，前一天持有股票或者前一天购买了股票
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};