代码随想录算法训练营第五十一天| 309 买卖股票的最佳时机含冰冻期 714 买卖股票的最佳时间含手续费

目录

309 买卖股票的最佳时机含冰冻期

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

309 买卖股票的最佳时机含冰冻期

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>>dp(prices.size() + 1,vector<int>(4));
        //dp[i][0]今天正持有股票
        //dp[i][1]今天度过冷冻期还未操作
        //dp[i][2]今天卖出了股票
        //dp[i][3]今天处于冷冻期
        dp[0][0] = - prices[0];//买入股票的花费
        for(int i = 1;i < prices.size();i++){
            dp[i][0] = max(dp[i - 1][0],max(dp[i - 1][1] - prices[i],dp[i - 1][3] - prices[i]));//今天正持有股票
            dp[i][1] = max(dp[i - 1][1],dp[i - 1][3]);//今天度过了冷冻期还未操作
            dp[i][2] = dp[i - 1][0] + prices[i];//今天卖出了股票
            dp[i][3] = dp[i - 1][2];//今天处于冷冻期
        }
        return max(max(dp[prices.size() - 1][1],dp[prices.size() - 1][2]),dp[prices.size() - 1][3]);//答案肯定不在dp[i][0]中
    }
};

时间复杂度O(n)

空间复杂度O(n)

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

?与 122 买卖股票的最佳时机 ||?思路相近

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0;
        int now = prices[0] + fee;
        for(int i = 1;i < prices.size();i++){
            if(now < prices[i]){//处于同一笔交易中
                res += prices[i] - now;
                now = prices[i];
            }else if(now > prices[i] + fee)now = prices[i] + fee;//开始下一次交易，加上手续费
        }
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(1)