table of Contents

• 121. The best time to buy and sell stocks
• • greedy
  • dp ideas
  • Scrolling array optimization
• 122. The Best Time to Buy and Sell Stocks II
• 123. The best time to buy and sell stocks III
• 188. The Best Time to Buy and Sell Stock IV
• 309. The best time to buy and sell stocks includes a freezing period
• 714. The best time to buy and sell stocks includes handling fees

121. The best time to buy and sell stocks

greedy

Take the leftmost minimum value, take the rightmost maximum value, and the difference is the maximum profit

class  Solution { 
public :
     int  maxProfit (vector< int >& prices)  {
         int n = prices. size ();
         int minprice = prices[ 0 ];
         int maxpro = 0 ;
         for ( int i = 1 ; i <n; i++ )
        {
            minprice = min (prices[i],minprice);
            maxpro = max (prices[i]-minprice,maxpro);
        }
        return maxpro;
    }
};
Copy code

dp ideas

step1:

Indicates the maximum cash from holding stocks on day i. In this question, you can only buy and sell once, so the amount after buying is.
Indicates that the maximum cash from holding stocks is not held on the i day. Holding is not the same as buying.
step2:
If you hold stocks on day iIt can be obtained from two states.
case1: The i-1th holds the stock and keep the status quo,
case2: If you buy stocks on the i day, the cash you get is the cash you get after buying today's stocks. which is
;
If no stocks are held on day iIt can be obtained from two states.
case1: The i-1th does not hold stocks, keep the status quo,
case2: hold the stock on the i-1, sell it on the i day,

step3: The
initial state is: Amount of stocks held on day 0 = -prices[0]
The amount of shares not held on day 0 = 0; the
final resultInstead of, Because in the end you must sell the stock to make a profit. If you don't sell, you will lose more.

class  Solution { 
public :
     int  maxProfit (vector< int >& prices)  {
         int n = prices. size ();
        vector<vector< int >> dp (n,vector< int >( 2 , 0 ));
        dp[ 0 ][ 0 ] = -prices[ 0 ];
        dp[ 0 ][ 1 ] = 0 ;
         for ( int i = 1 ; i <n; i++)
        {
            //holds 
            DP [I] [ 0 ] = max (DP [I -1 ] [ 0 ], - Prices [I]);
             //not holding 
            DP [I] [ . 1 ] = max (DP [I - 1 ][ 1 ],dp[i -1 ][ 0 ]+prices[i]);
        }
        return dp[n -1 ][ 1 ];
    }
};
Copy code

Scrolling array optimization

Since only two states of dp[i] and dp[i-1] are used, only a 2 * 2 array is needed.

class  Solution { 
public :
     int  maxProfit (vector< int >& prices)  {
         int n = prices. size ();
        vector<vector< int >> dp ( 2 ,vector< int >( 2 , 0 ));
        dp[ 0 ][ 0 ] = -prices[ 0 ];
        dp[ 0 ][ 1 ] = 0 ;
         for ( int i = 1 ; i <n; i++)
        {
            //Hold 
            dp[i% 2 ][ 0 ] = max (dp[(i -1 )% 2 ][ 0 ],-prices[i]);
             //Do not hold 
            dp[i% 2 ][ 1 ] = max (dp[(i -1 )% 2 ][ 1 ],dp[(i -1 )% 2 ][ 0 ]+prices[i]);
        }
        return dp[(n -1 )% 2 ][ 1 ];
    }
};
Copy code

122. The Best Time to Buy and Sell Stocks II

: Maximum cash obtained from holding stocks on day i
: The maximum amount of cash earned from not holding stocks on
the ith day If you hold stocks on the ith day, thenIt can be deduced from two states;
case1: hold the stock on day i-1 and maintain the status quo, then
case2: The stock is bought on the i day, and the cash is the cash that did not hold the stock yesterday minus the stock price today
If no stock is held on day i, thenIt can be deduced from two states;
case1: do not hold stocks on day i-1, keep the status quo,
case2: hold stock on day i-1, sell on day i,

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

123. The best time to buy and sell stocks III

It can be bought and sold twice at most, either once or twice, or not.
Each day consists of five states:
0, no operation,
1, first purchase
2, first sale
3, second purchase
4, second sale

:i means the i-th day, j is the five states [0-4],Represents the maximum cash left in state j on the i-th day.

2, it is determined recursion formulas
Examples

: Indicates the status of buying stocks on the i day, but it does not mean that stocks must be bought on the i day.
achieveStatus, there are two specific operations:
case1: buy stocks on the i day, then
case2: There is no operation on the i day, then
; The
same reasonThere are also two operations:
case1: the stock is sold on the i day, then
case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:
and so
The sameThere are also two operations:
case1: buy stocks on the i day,
case2: There is no operation on the i day, and the state of buying the stock the day before is used, namely:
The sameThere are also two operations:
case1: sell the stock on the i day,
case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:
So how to initialize it?
If there is no operation on day 0,
If you do the first buy operation on day 0,
Do the first sell operation on day 0, and this initial value is 0.
Buy the second time on day 0, no matter how many times, there is no money on hand, you can only reduce
Sell for the second time on day 0,

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

188. The Best Time to Buy and Sell Stock IV

step1:
This question is an advanced version of the previous question, which defines a two-dimensional dp array.
Use a two-dimensional array

: The state on the i-th day is j, and the largest cash remaining is
The status of j is expressed as:
0 no operation, 1 first purchase, 2 first sale, ...
Except for 0, even numbers are selling, and odd numbers are buying. Because there are at most k transactions, the range of j is defined as 2*k+1.

Vector <Vector < int >> DP (Prices. size (), Vector < int > ( 2 * K + . 1 , 0 ));
 duplicated code

step2:

for ( int j = 0 ; j < 2 * k- 1 ; j+= 2 )
{
    //Odd, indicating to buy 
    dp[i][j+ 1 ] = max (dp[i -1 ][j+ 1 ],dp[i -1 ][j]-prices[i]);
     //even, indicating Sell 
    dp[i][j+ 2 ] = max (dp[i -1 ][j+ 2 ],dp[i -1 ][j+ 1 ] + prices[i]);
}
Copy code

step3:
Initialization, as long as it is a buying operation, the cash will be reduced accordingly, and the initial value of the selling operation will be 0

for ( int j = 1 ; j < 2 *k; j += 2 )
{
    dp[ 0 ][j] = -prices[ 0 ];
}
Copy code

AC code:

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

309. The best time to buy and sell stocks includes a freezing period

State 1: The state of buying stocks (maybe it was bought today, or it may have been bought before and then no operation)
. There are two
states of selling stocks: State 2: The stock was sold two days ago, degree after a freezing period and has not been operating, selling stock today remains state
state three: today sold stock
status four: today is the freezing of the state, but the frozen state of unsustainable, only one day
recurrence formula is as follows:
arrival buy Into the stock status (status 1) namely

, There are two specific operations:
case1: It was in this state the day before, and this state is used today
Case2: Buy today, there are two situations (state 4) the
previous day was the freezing period, and the previous day was the state of keeping the stock sold (state 2), both of which are possible to buy today
, namely:
Reaching the state of keeping sold (state two) namely:, There are two specific operations:
case1: the previous day is the second state, and continue to use this state
case2: the previous day is the freezing period (state four)

It reaches the state of selling stocks today (state three), there is only one state, the previous day was state one, and then selling today

The freezing period state (state 4) has been reached, there is only one state, and the stock has just been sold the day before

In summary, the recurrence code is:

dp[i][ 0 ] = max (dp[i -1 ][ 0 ], max (dp[i -1 ][ 3 ],dp[i -1 ][ 1 ])-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 ];
 Copy code

Regarding the initialization of the dp array:
state one, holding stocks, then

Status two, keep selling status,
State three, just sold the stock, there will be no income either
State four, freezing period,
The final result is to select the maximum value from state two to state four.

class  Solution { 
public :
     int  maxProfit (vector< int >& prices)  {
         int n = prices. size ();
        vector<vector< int >> dp (n,vector< int >( 4 , 0 ));
        dp[ 0 ][ 0 ] = -prices[ 0 ];
         for ( int i = 1 ; i <n; i++)
        {
            dp[i][ 0 ] = max (dp[i -1 ][ 0 ], max (dp[i -1 ][ 1 ],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 (dp[n -1 ][ 1 ], max (dp[n -1 ][ 2 ],dp[n -1 ][ 3 ]));
    }
};
Copy code

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

Compared with 122. The best time to buy and sell stocks II, subtract more operating expenses.

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

    }
};
Copy code