Dynamic programming stock problem comparison

Core or state transition , It's easy to figure out what each state is
If you don't know the transfer process, you can make a watch

From here dp[i][j],i from 1 At first, it's because I habitually want to avoid i-1 Lead to cross-border

1

121. The best time to buy and sell stocks

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

The finger of the sword Offer 63. The biggest profit of stocks

What is the maximum profit that can be obtained by buying and selling this stock at one time ？

analysis ：

These two questions are the same , You can only buy and sell once
The following two methods just think from different angles ：
1.dp[i][0] and dp[i][1] Respectively represents no shares （ Maybe I didn't buy , It may be sold ）、 There are stocks （ Only once , Therefore, the last value cannot be superimposed ） Two kinds of state
%2 It's a way to save space , Can not add
2.
dp[i][0] Never bought it
dp[i][1] I bought it once , And not sold
dp[i][2] I bought it once , And sell

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int len=prices.size();
        vector<vector<int>>dp(2,vector<int>(2,0));
        int ans=0;
        dp[1][0]=0;
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
    
            dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i-1]);
            dp[i%2][1]=max(dp[(i-1)%2][1],-prices[i-1]);

            
        }
        return dp[len%2][0];

    }
};

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int len=prices.size();
        if(len==0)return 0;
        vector<vector<int>>dp(len+1,vector<int>(3,0));
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
    
            dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][0]-prices[i-1],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][1]+prices[i-1],dp[i-1][2]);
        }
        return dp[len][2];
    }
};

2

122. The best time to buy and sell stocks II

Give you an array of integers prices , among prices[i] Represents a stock i Sky price .

Every day , You can decide whether to buy and / Or sell shares . You at any time most Can only hold A wave of Stocks . You can also buy... First , And then in On the same day sell .

return What you can get Maximum profits .

analysis ：

and 1 comparison , You can buy and sell many times , It means that buying can superimpose the last state

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(2,0));
        dp[1][1]=-prices[0];
        dp[1][0]=0;
        for(int i=2;i<=len;i++){
    
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
            
        }
        return dp[len][0];
        
    }
};

3

123. The best time to buy and sell stocks III

Given an array , It's the first i An element is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most Two pens transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

analysis ：

and 2 comparison , Limit the number of purchases , You can only buy twice
Just use 5 Status flags
dp[i][0] Never bought it
dp[i][1] I bought it once , And hold
dp[i][2] I bought it once , And sold
dp[i][3] I bought it twice , And hold
dp[i][4] I bought it twice , And sold

Note initialization , You can buy and sell and buy all day

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(5,0));
        
        dp[1][1]=-prices[0];
        // Note that you can buy and sell twice a day 
        dp[1][3]=-prices[0];
        for(int i=2;i<=len;i++){
    
            dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][0]-prices[i-1],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][1]+prices[i-1],dp[i-1][2]);
            dp[i][3]=max(dp[i-1][2]-prices[i-1],dp[i-1][3]);
            dp[i][4]=max(dp[i-1][3]+prices[i-1],dp[i-1][4]);
            


        }
        return dp[len][4];


    }
};

4

188. The best time to buy and sell stocks IV

Given an array of integers prices , It's the first i Elements prices[i] Is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most k transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）

analysis ：

and 3 comparison , Buy twice and change k Time
Just use 2k+1 Status flags
dp[i][0] Never bought it
dp[2i+1][1] I bought it once , And hold
dp[ik+2][2] I bought it once , And sold
Then the cycle is over

Note initialization , You can buy, sell, buy and …

class Solution {
    
public:
    int maxProfit(int k, vector<int>& prices) {
    
        int len=prices.size();
        if(len==0)return 0;
        vector<vector<int>>dp(len+1,vector<int>(2*k+1,0));
        for(int i=0;i<k;i++){
    
            dp[1][2*i+1]=-prices[0];
        }
        for(int i=2;i<=len;i++){
    
            dp[i][0]=dp[i-1][0];
      
            for(int j=0;j<k;j++){
    
                dp[i][2*j+1]=max(dp[i-1][2*j]-prices[i-1],dp[i-1][2*j+1]);
                dp[i][2*j+2]=max(dp[i-1][2*j+1]+prices[i-1],dp[i-1][2*j+2]);
            }
        }
        return dp[len][2*k];
       
    }
};

5

714. The best time to buy and sell stocks includes handling fees

Given an array of integers prices, among prices[i] It means the first one i Day's share price ; Integers fee Represents the handling fee for trading shares .

You can close the deal indefinitely , But you have to pay a handling fee for every transaction . If you have bought a stock , You can't buy any more stock until you sell it .

Return the maximum profit .

Be careful ： A deal here refers to the whole process of buying, holding and selling stocks , You only need to pay a handling fee for each transaction .

analysis ：

Follow 2 comparison , At the time of sale -fee Just go

class Solution {
    
public:
    int maxProfit(vector<int>& prices, int fee) {
    
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(2,0));
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
    
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i-1]-fee);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
        }
        return dp[len][0];
    }
};