股票买卖问题

买卖股票的最佳时机相关问题

121. 买卖股票的最佳时机

只能交易一次

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> dp0(n); //当天不持有股票
        vector<int> dp1(n); //当天持有股票

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], -prices[i]);
        }
        return dp0[n-1];
    }
};

122. 买卖股票的最佳时机 II

交易次数不限

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> dp0(n); //当天没有持有股票
        vector<int> dp1(n); //当天持有股票

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], dp0[i-1]-prices[i]);
        }
        return dp0[n-1];
    }
};

123.买卖股票的最佳时机 III

最多交易两次

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp0(n,vector<int>(3));
        vector<vector<int>> dp1(n,vector<int>(3));

        //base case
        for(int i=1;i<=2;i++){
            dp0[0][i]=0;
            dp1[0][i]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int j=2;j>0;j--){
                dp0[i][j]=max(dp0[i-1][j], dp1[i-1][j]+prices[i]);
                dp1[i][j]=max(dp1[i-1][j], dp0[i-1][j-1]-prices[i]);
            }
        }
        return dp0[n-1][2];
    }
};

188.买卖股票的最佳时机 IV

最多可以交易k次

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n==0) return 0;
        // k = min(n/2, k);
        vector<vector<int>> dp0(n,vector<int>(k+1));
        vector<vector<int>> dp1(n,vector<int>(k+1));

        //base case
        for(int i=1;i<=k;i++){
            dp0[0][i]=0;
            dp1[0][i]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int j=k;j>0;j--){
                dp0[i][j]=max(dp0[i-1][j], dp1[i-1][j]+prices[i]);
                dp1[i][j]=max(dp1[i-1][j], dp0[i-1][j-1]-prices[i]);
            }
        }
        return dp0[n-1][k];
    }
};

309.最佳买卖股票时机含冷冻期

交易次数不限，含冷冻期

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<=1) return 0;
        vector<int> dp0(n);
        vector<int> dp1(n);
        
        //base case
        dp0[0]=0;
        dp1[0]=-prices[0];
        dp0[1]=max(dp0[0], dp1[0]+prices[1]);
        dp1[1]=max(dp1[0], -prices[1]);
        
        for(int i=2;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], dp0[i-2]-prices[i]);
        }
        return dp0[n-1];
    }
};

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

交易次数不限，含手续费

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<int> dp0(n);
        vector<int> dp1(n);

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0]-fee;

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], dp0[i-1]-prices[i]-fee);
        }
        return dp0[n-1];
    }
};