仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

股票买卖问题

发表于 更新于 分类于 ， ，
本文字数： 2.9k 阅读时长 ≈ 3 分钟

【道德经·第三十三章】知人者智，自知者明。胜人者有力，自胜者强。知足者富，强行者有志，不失其所者久，死而不亡者寿。

本文代码参考自：HReina的博客

121. 买卖股票的最佳时机

只能交易一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

交易次数不限

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

最多交易两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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]);
                // 0-->1：买入操作，交易次数：j-1-->j
                dp1[i][j]=max(dp1[i-1][j], dp0[i-1][j-1]-prices[i]);
            }
        }
        return dp0[n-1][k];
    }
};

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

交易次数不限，含冷冻期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.买卖股票的最佳时机含手续费

交易次数不限，含手续费

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
    }
};

位我上者，灿烂星空；道德律令，在我心中。