The idea of this paper is from the English version LeetCode Answer key ：
After reading this article , You can go and get the following questions ：
The best time to buy and sell stocks
The best time to buy and sell stocks II
The best time to buy and sell stocks III
The best time to buy and sell stocks IV
The best time to buy and sell stocks includes the freezing period
The best time to buy and sell stocks includes handling fees
-----------
Many readers complain about LeetCode There are too many problems in the stock series , If the interview does encounter such problems , I don't think of those ingenious methods , What do I do ？ Therefore, this article refuses to be skillful , It's about being steady , Use only one general method to solve the problem used , Maintaining the status quo .
This article uses state machine techniques to solve , All can be submitted through . Don't think the term is tall , Literary vocabulary is just , It's actually DP table, You can see at a glance .
this 6 There is something in common , I'll take out the first one 4 questions , Because this problem is the most general form , Other problems are the simplification of this form , Look at the title ：
The first is to make only one transaction , amount to k = 1; The second question is no limit to the number of transactions , amount to k = +infinity（ It's just infinite ）; The third question is just to carry on 2 Transactions , amount to k = 2; The other two are unlimited , But with the deal 「 Freezing period 」 and 「 Service Charge 」 Additional conditions for , In fact, it's a variation of the second question , It's easy to deal with .
If you're not familiar with the topic , You can go to LeetCode Look at the content of these topics , In order to save space , Let's not list the specific contents of these topics . Let's get down to business , Start solving the problem .
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
One 、 The framework of exhaustion
First , The same way of thinking ： How to exhaust ？ The idea of exhausting here is different from that of recursion in the previous article .
Recursion is actually in line with the logic of our thinking , Step by step , If you encounter something that can't be solved, throw it to recursion , It was done by accident , Readability is good . The disadvantage is that once something goes wrong , It's not easy for you to find the cause of the error . For example, the recursive solution of the previous article , There must be computational redundancy , But it's not easy to find .
And here , We don't use recursion to enumerate , But the use of 「 state 」 To exhaust . We go to every day , Look at all the possibilities 「 state 」, Find out each one 「 state 」 Corresponding 「 choice 」. We want to exhaust all 「 state 」, The purpose of exhaustion is based on the corresponding 「 choice 」 Update status . Sounds abstract , You just have to remember 「 state 」 and 「 choice 」 Just two words , Now it's easy to understand with practice .
for state 1 in state 1 All values of ：
for state 2 in state 2 All values of ：
for ...
dp[ state 1][ state 2][...] = preferential ( choice 1, choice 2...)
Let's say this question , There are three kinds of... Every day 「 choice 」： purchase 、 sell 、 No operation , We use it buy, sell, rest Show these three options . But the problem is , Not every day you can choose any of these three options , because sell Must be in buy after ,buy Must be in sell after . that rest There are also two states of operation , One is buy After that rest（ Holding shares ）, One is sell After that rest（ No shares ）. And don't forget , We still have the number of transactions k The limitation of , That means you buy Also can only be k > 0 Under the premise of operation .
It's complicated, right , Don't be afraid of , Our aim now is to be poor , You have more state , What I have to do is to list all the shuttles . Of this question 「 state 」 There are three , The first is the number of days , The second is the maximum number of transactions allowed , The third is the current holding status （ That's what I said before rest The state of , We might as well use 1 To hold ,0 To indicate that you do not hold ）. Then we can use a three-dimensional array to hold all the combinations of these States ：
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n For days , Big K For the maximum number of transactions
This question altogether n × K × 2 States , It's all done with poverty .
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
And we can use natural language to describe the meaning of each state , for instance dp[3][2][1] That means ： Today is the third day , I have stock in my hand now , Up to now, it's the most 2 Transactions . Another example dp[2][3][0] The meaning of ： Today is the next day , I don't have any stock in my hand now , Up to now, it's the most 3 Transactions . It's easy to understand , Right ？
The final answer we want is dp[n - 1][K][0], The last day , Most allow K Transactions , How much profit do you get at most . Readers may ask why not dp[n - 1][K][1]？ because [1] The representative still holds shares ,[0] It means that the stock in hand has been sold , Obviously, the profit of the latter must be greater than that of the former .
Remember how to explain 「 state 」, Once you feel something is not easy to understand , It's easy to understand by translating it into natural language .
Two 、 State transition framework
Now? , We finished 「 state 」 Poverty of , We began to think about every kind of 「 state 」 What are they? 「 choice 」, How to update 「 state 」. Just look at 「 Holding state 」, You can draw a state transition diagram .
You can see clearly through this picture , Every state （0 and 1） How it was transferred . According to this picture , Let's write the equation of state transition ：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( choice rest , choice sell )
explain ： I don't own shares today , There are two possibilities ：
Or I didn't hold it yesterday , Then choose today rest, So I still don't hold ;
Or I held shares yesterday , But today I sell 了 , So I don't have any shares today .
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( choice rest , choice buy )
explain ： Today I hold shares , There are two possibilities ：
Or I had stocks yesterday , Then choose today rest, So I still have stocks today ;
Or I didn't have it yesterday , But today I choose buy, So today I hold shares .
The explanation should be clear , If buy, It's about subtracting... From the profits prices[i], If sell, To increase profits prices[i]. Today's biggest profit is the larger of the two possible options . And pay attention to k The limitation of , We are choosing buy When , hold k Reduced 1, It's easy to understand , Of course you can be in sell When it's time 1, Same .
Now? , We have completed the most difficult step in dynamic planning ： State transition equation . If you can understand the previous content , Then you can kill all the problems , Just set the frame . But it's just a little short of the last , It's the definition of base case, In the simplest case .
dp[-1][k][0] = 0
explain ： because i It's from 0 At the beginning , therefore i = -1 It means it hasn't started yet , The profit at this time is of course 0 .
dp[-1][k][1] = -infinity
explain ： Before we started , It's impossible to hold shares , To express the impossibility with negative infinity .
dp[i][0][0] = 0
explain ： because k It's from 1 At the beginning , therefore k = 0 It means that trading is not allowed at all , At this time, of course, the profit is 0 .
dp[i][0][1] = -infinity
explain ： When trading is not allowed , It's impossible to hold shares , To express the impossibility with negative infinity .
Let's summarize the above equation of state transfer ：
base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
State transition equation ：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
The reader may ask , The index of this array is -1 How to program it out , How to express negative infinity ？ It's all about details , There are many ways to do this . Now the complete framework is complete , Let's start to concretize .
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
3、 ... and 、 Second kill the problem
The first question is ,k = 1
A direct set of state transfer equations , according to base case, You can do some simplification ：
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
= max(dp[i-1][1][1], -prices[i])
explain ：k = 0 Of base case, therefore dp[i-1][0][0] = 0.
Now find k All are 1, Will not change , namely k It has no effect on state transition .
It can be further simplified to remove all k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
Write the code directly ：
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
obviously i = 0 when dp[i-1] It's illegal . This is because we are not right i Of base case To deal with . You can do this ：
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
dp[i][0] = 0;
// explain ：
// dp[i][0]
// = max(dp[-1][0], dp[-1][1] + prices[i])
// = max(0, -infinity + prices[i]) = 0
dp[i][1] = -prices[i];
// explain ：
// dp[i][1]
// = max(dp[-1][1], dp[-1][0] - prices[i])
// = max(-infinity, 0 - prices[i])
// = -prices[i]
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
The first problem is solved , But deal with it like this base case so much trouble , And notice the equation of state transfer , The new state is only related to one adjacent state , It doesn't have to be the whole thing dp Array , Only one variable is needed to store the adjacent state , This can reduce the space complexity to O(1):
// k == 1
int maxProfit_k_1(int[] prices) {
int n = prices.length;
// base case: dp[-1][0] = 0, dp[-1][1] = -infinity
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
// dp[i][1] = max(dp[i-1][1], -prices[i])
dp_i_1 = Math.max(dp_i_1, -prices[i]);
}
return dp_i_0;
}
Both ways are the same , But it's a lot simpler . But without the guidance of the previous equation of state transition , I can't understand it . Follow up questions , I mainly write about this kind of spatial complexity O(1) Solution method .
The second question is ,k = +infinity
If k For Infinity , Then we can think of k and k - 1 It's the same . You can rewrite the framework like this ：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
= max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
We found... In the array k It won't change , That is to say, there is no need to record k This is the state ：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
Translate directly into code ：
int maxProfit_k_inf(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}
Third question ,k = +infinity with cooldown
Every time sell It's going to take a day for the deal to continue . As long as this feature is integrated into the state transfer equation of the previous problem ：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
explain ： The first i God choose buy When , From you to i-2 State transition of , instead of i-1 .
Translate into code ：
int maxProfit_with_cool(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
int dp_pre_0 = 0; // representative dp[i-2][0]
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
Fourth question ,k = +infinity with fee
There is a handling charge for every transaction , Just subtract the commission from the profit . Rewrite the equation ：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
explain ： The price of buying a stock has gone up .
It's the same thing to subtract in the first formula , The price equivalent to selling shares has decreased .
Translate directly into code ：
int maxProfit_with_fee(int[] prices, int fee) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
}
return dp_i_0;
}
Fifth question ,k = 2
k = 2 It's slightly different from the previous topic , Because it's all the same k It doesn't matter much . or k It's just infinite , State shifting and k It doesn't matter ; or k = 1, Follow k = 0 This base case Get close to , Finally, there is no sense of existence .
This question k = 2 And what I'm going to talk about later k In the case of any positive integer , Yes k And the treatment of . We write code directly , Analyze the reasons while writing .
The original dynamic transfer equation , There is no place to simplify
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
Follow the previous code , We may take it for granted to write code like this （ FALSE ）：
int k = 2;
int[][][] dp = new int[n][k + 1][2];
for (int i = 0; i < n; i++)
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
return dp[n - 1][k][0];
Why is it wrong ？ I wrote this according to the equation of state transition ？
Remember what I summarized earlier 「 The framework of exhaustion 」 Do you ？ That means we have to exhaust all States . In fact, our previous solution , All States are being impoverished , Just in the previous topic k It's all simplified . The problem is not eliminated k Influence , So we have to be right k To exhaust ：
int max_k = 2;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++) {
for (int k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
// Exhausted n × max_k × 2 Status , correct .
return dp[n - 1][max_k][0];
If you don't understand , You can go back to the first point 「 The framework of exhaustion 」 Reread and experience .
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
here k The value range is relatively small , So you don't have to for loop , Put... Directly k = 1 and 2 It's OK to enumerate all the situations ：
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][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
int maxProfit_k_2(int[] prices) {
int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
for (int price : prices) {
dp_i20 = Math.max(dp_i20, dp_i21 + price);
dp_i21 = Math.max(dp_i21, dp_i10 - price);
dp_i10 = Math.max(dp_i10, dp_i11 + price);
dp_i11 = Math.max(dp_i11, -price);
}
return dp_i20;
}
There are state transfer equations and variable names with clear meanings , I believe it's easy for you to understand . In fact, we can make mysteries , Replace the four variables with a, b, c, d. This will make people look pale when they see your code , I have great respect for you .
Sixth question ,k = any integer
With the last question k = 2 The bedding of , This problem should be no different from the first solution of the previous one . But there was a super memory error , It turned out to be an incoming k It's going to be worth a lot ,dp The array is too big . Now think about it. , Number of transactions k How big is it at most ？
A transaction consists of buying and selling , It will take at least two days . So effective restrictions k Should not exceed n/2, If exceeded , There is no binding effect , amount to k = +infinity. This situation has been solved before .
Reuse the previous code directly ：
int maxProfit_k_any(int max_k, int[] prices) {
int n = prices.length;
if (max_k > n / 2)
return maxProfit_k_inf(prices);
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++)
for (int k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
return dp[n - 1][max_k][0];
}
thus ,6 The problem is solved by a state transfer equation .
Four 、 The final summary
This article tells you how to solve complex problems through state transition , Use a state transfer equation to kill 6 The problem of trading stocks , Now think about it. , It's not hard, is it ？ This is already one of the more difficult problems in dynamic planning .
The key is to list all the possible 「 state 」, And then think about how to update these exhaustively 「 state 」. We usually use a multi dimension dp Arrays store these States , from base case Start pushing back , Advance to the final state , It's the answer we want . Think about the process , Do you have some understanding of 「 Dynamic programming 」 What's the meaning of this noun ？
Specific to the issue of stock trading , We found three states , Used a three-dimensional array , It's just poverty + to update , But we can say it's a little bit bigger , This is called 「 The three dimensional DP」.
＿＿＿＿＿＿＿＿＿＿＿＿＿
Click on My home page Read more quality articles .
