"Dp card replenishment-the issue of buying and selling stocks"

"Dp card replenishment-the issue of buying and selling stocks"

table of Contents

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:

dp[i][0]
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
-price[i]
.
dp[i][1]
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 i
dp[i][0]
It can be obtained from two states.
case1: The i-1th holds the stock and keep the status quo,
dp[i][0] = dp[i-1][0]

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
dp[i][0] = -price[i]

dp[i][0] = max(dp[i-1][0],-price[i])
;
If no stocks are held on day i
dp[i][1]
It can be obtained from two states.
case1: The i-1th does not hold stocks, keep the status quo,
dp[i][1] = dp[i-1][1]

case2: hold the stock on the i-1, sell it on the i day,
dp[i][1] = dp[i-1][0] + price[i]

dp[i][1] = max(dp[i-1][1],dp[i-1][0]+price[i])

step3: The
initial state is
dp[0][0]
: Amount of stocks held on day 0 = -prices[0]
dp[0][1]
The amount of shares not held on day 0 = 0; the
final result
dp[n][1]
Instead of
dp[n][0]
, 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

dp[i][0]
: Maximum cash obtained from holding stocks on day i
dp[i][1]
: The maximum amount of cash earned from not holding stocks on
the ith day If you hold stocks on the ith day, then
dp[i][0]
It can be deduced from two states;
case1: hold the stock on day i-1 and maintain the status quo, then
dp[i][0] = dp[i-1][0]

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
dp[i][0] = dp[i-1][1]-prices[i]

If no stock is held on day i, then
dp[i][1]
It can be deduced from two states;
case1: do not hold stocks on day i-1, keep the status quo,
dp[i][1] = dp[i-1][1]

case2: hold stock on day i-1, sell on day i,
dp[i][1] = dp[i-1][0] + prices[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

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

2, it is determined recursion formulas
Examples

dp[i][1]
: Indicates the status of buying stocks on the i day, but it does not mean that stocks must be bought on the i day.
achieve
dp[i][1]
Status, there are two specific operations:
case1: buy stocks on the i day, then
dp[i][1] = dp[i-1][0]-prices[i]

case2: There is no operation on the i day, then
dp[i][1] = dp[i-1][1]

dp[i-1][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])
; The
same reason
dp[i][2]
There are also two operations:
case1: the stock is sold on the i day, then
dp[i][2] = dp[i-1][1] + prices[i]

case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:
dp[i][2] = dp[i-1][2]

and so
dp[i][2] = max(dp[i-1][1] + prices[i],dp[i-1][2])

The same
dp[i][3]
There are also two operations:
case1: buy stocks on the i day,
dp[i][3] = dp[i-1][2]-prices[i]

case2: There is no operation on the i day, and the state of buying the stock the day before is used, namely:
dp[i][3] = dp[i-1][3]

The same
dp[i][4]
There are also two operations:
case1: sell the stock on the i day,
dp[i][4] = dp[i-1][3] + prices[i]

case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:
dp[i][4] = dp[i-1][4]

So how to initialize it?
If there is no operation on day 0,
dp[0][0] = 0

If you do the first buy operation on day 0,
dp[0][1] = -prices[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
dp[0][3] = -prices[0]

Sell for the second time on day 0,
dp[0][4] = 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

dp[i][j]
: The state on the i-th day is j, and the largest cash remaining is
dp[i][j]

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

dp[i][0]
, There are two specific operations:
case1: It was in this state the day before, and this state is used today
dp[i][0] = dp[i-1][0]

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

Reaching the state of keeping sold (state two) namely:
dp[i][1]
, 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)
dp[i][1] = max(dp[i-1][1],dp[i-1][3])

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
dp[i][2] = dp[i-1][0] + prices[i]

The freezing period state (state 4) has been reached, there is only one state, and the stock has just been sold the day before
dp[i][3] = dp[i-1][2]

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

dp[0][0] = -prices[0]

Status two, keep selling status,
dp[0][1] = 0

State three, just sold the stock, there will be no income either
dp[0][2] = 0

State four, freezing period,
dp[0][3] = 0

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