LeetCode (English version)
Leetcode.com/problems/be…
After reading this article, you can try to solve 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 or sell stocks includes a freeze period
The best time to buy and sell stocks includes fees
———–
Many readers have complained that LeetCode’s stock questions are too tricky. What if you don’t come up with clever answers to these questions? Therefore, this paper refuses to be crafty, but to play it slow and steady, using only a general method to solve the problem, in order to change.
This article uses the skill of state machine to solve, can submit all pass. Don’t think this term is lofty, just a literary word, actually is DP table, look at it.
These six questions have something in common, so I’m going to pull out the fourth question, because this is the most general form, and the other questions are all simplifications of this form. Let’s look at the question:
The first one is only one transaction, which is k = 1; K = +infinity (+infinity); The third one is only 2 transactions, which is equal to k = 2; The remaining two questions are also unlimited, but with the additional conditions of “frozen period” and “handling fee”, which are actually variations of the second question, they are easy to handle.
If you’re not familiar with the topics, you can check them out at LeetCode. To save space, I won’t list them in this article. So let’s get back to the problem.
PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.
First, exhaustive framework
First, the same idea: how do you do it? The exhaustive thinking here is not quite the same as the recursive idea in the previous article.
Recursion is actually in line with the logic of our thinking, step by step, encounter can not solve the recursion, accidentally made, very readable. The downside is that once you make a mistake, it’s not easy to figure out why it happened. For example, the recursive solution in the previous article, there is certainly computational redundancy, but it is really not easy to find.
And here, instead of doing it recursively, we’re doing it using states. Let’s take a day at a time, look at how many possible “states” there are, and identify the “choices” for each state. We enumerate all the “states”, and the purpose of enumeration is to update the states according to the corresponding “choices”. As abstract as it sounds, you just need to remember the words “state” and “choice”, and it’s easy to see why.
forstate1 instate1All values of:forstate2 instate2All values of:for. Dp [state1] [state2] [...]. = Choose the best1, the choice of2...)
Copy the codeFor example, every day there are three “choices” : buy, sell, and no action. We use buy, sell, and REST to represent these three choices. But the problem is that you can’t choose any of these three options every day, because sell has to come after buy, and buy has to come after sell. The REST operation should also have two states: REST after Buy (holding the stock) and REST after sell (not holding the stock). And don’t forget, we also have a limit of k transactions, which means you can only buy if K is greater than 0.
It is very complicated, right? Don’t be afraid, our purpose now is just to enumerate, no matter how many states you have, the old man should do is to enumerate all of them in a shuttle. There are three “states” of this problem, the first is the number of days, the second is the maximum number of transactions allowed, and the third is the current holding state (the previous state of REST, we might as well use 1 for holding and 0 for not holding). We can then use a three-dimensional array to hold all combinations of these states:
dp[i][k][0 or 1]
0 <= i <= n-1.1<= k <= k N indicates the number of days, and k indicates the maximum number of transactions. The total number of transactions in this problem is N x K x2All of them, all of them.for 0 <= i < n:
for 1 <= k <= K:
for s in {0.1}:
dp[i][k][s] = max(buy, sell, rest)
Copy the codeIn addition, we can use natural language to describe the meaning of each state. For example, dp[3][2][1] means: today is the third day, I am holding stocks and have traded at most two times so far. For example, the meaning of DP [2][3][0] : Today is the second day, I have no stock on hand, so far I have traded three times at most. Easy to understand, right?
The final answer we want to find is dp[n-1][K][0], that is, the last day, the maximum number of transactions allowed, how much profit can be made. The reader may ask why not DP [n-1][K][1]? Since [1] means still holding stock and [0] means the stock has been sold, it is obvious that the profit of the latter must be greater than the former.
Remember how to interpret “states,” and once you find something difficult to understand, translate it into natural language.
Second, state transition framework
Now that we’ve exhausted our states, we can start thinking about the “choices” for each state and how to update our states. Just look at “holding states,” and you can draw a state transition diagram.
It is clear from this diagram how each state (0 and 1) is transferred. Based on this graph, let’s write the state transition equation:
Dp [I][k][0] = Max (dp[i-1][k][0], dp[i-1][k][1] + prices[I]) Max Either I didn't hold it yesterday, and I chose REST today, so I still don't hold it today; Or I owned the stock yesterday, but I sold it today, so I don't own the stock today. Dp [I][k][1] = Max (dp[i-1][k][1], dp[i-1][K-1][0] -prices [I]) Max (select rest, select buy) Either I owned the stock yesterday, and I chose REST today, so I still own the stock today; Or I didn't own the stock yesterday, but today I choose buy, so I own the stock today.Copy the codeThe explanation should be pretty clear, if you buy, you subtract prices[I] from the profit, and if you sell, you add prices[I] to the profit. The biggest profit today is the greater of these two possibilities. And notice the limit on k, when we select buy, we decrease k by 1, which makes sense, but you can also decrease k by 1 when you sell, same thing.
We have now completed the most difficult step in dynamic programming: the state transition equation. ** If you can understand the previous content, then you can already kill any problems, just use this framework. ** But there is one last bit left, which is to define the base case, the simplest case.
Dp [-1][k][0] = 0 Dp [-1][k][1] = -infinity explanation: it is impossible to own the stock before it has started, denoted by negative infinity. Dp [I][0][0] = 0 explanation: since k starts at 1, k = 0 means that trading is not allowed at all, in which case profit is of course 0. Dp [I][0][1] = -infinity explanation: it is impossible to own a stock without trading, denoted by negative infinity.Copy the codeTo summarize the state transition equation above:
The base case: dp [1] [k] [0] = dp [I] [0] [0] = 0 dp [1] [k] [1] = dp [I] [0] [1] = - infinity state transfer 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])Copy the codeThe reader might ask, how do I programmatically represent this array index minus 1, and how do I programmatically represent minus infinity? It’s all in the details. There are many ways to do it. Now that the complete framework is complete, it’s time to materialize.
PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.
Three, second to kill the topic
Problem number one, k is equal to 1
According to the base case, some simplifications can be made:
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]) explanation: k = 0 base case, so dp [0] [I - 1] [0] = 0. Now we find that k is always 1 and will not change, that is, k has no effect on state transition. Can be further reduced to remove all k: dp [I] [0] = Max (dp [0], [I - 1] dp] [I - 1 + prices [1] [I]) dp [I] [1] = Max (dp [1], [I - 1] - prices [I])Copy the codeWrite 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];
Copy the codeObviously dp[I -1] is illegal when I = 0. This is because we didn’t process the base case of I. It can be handled like this:
for (int i = 0; i < n; i++) {
if (i - 1= = -1) {
dp[i][0] = 0;
/ / interpretation:
// dp[i][0]
// = max(dp[-1][0], dp[-1][1] + prices[i])
// = max(0, -infinity + prices[i]) = 0
dp[i][1] = -prices[i];
/ / interpretation:
// 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];
Copy the codeThe new state is only related to the neighboring state. In fact, instead of the entire DP array, only one variable is needed to store the neighboring 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;
}
Copy the codeBoth ways are the same, but this programming method is much cleaner. But you wouldn’t be able to understand it without the state transition equation. In the next few problems, I’m going to write mainly about this space O(1) solution.
Number two, k is equal to plus infinity
If k is infinity, then k and k minus 1 are the same thing. 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]) 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])
Copy the codeTranslate 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;
}
Copy the codeProblem 3, k = +infinity with cooldown
You have to wait a day after each sell to continue trading. Just incorporate this feature into the state transition equation of the previous problem:
Dp [I] [0] = Max (dp [0], [I - 1] dp] [I - 1 + prices [1] [I]) dp [I] [1] = Max (dp [1], [I - 1] dp [0] - [I - 2] prices [I]) : On day I, when you select Buy, you need to move from i-2, not i-1.Copy the codeTranslated 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; / / on behalf of the 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;
}
Copy the codeK = +infinity with fee
Each transaction pays a fee, which can be subtracted from the profit. Rewrite the equation:
Dp [I] [0] = Max (dp [0], [I - 1] dp] [I - 1 + prices [1] [I]) dp [I] [1] = Max (dp [1], [I - 1] dp [0] - [I - 1] prices [I] - fee) : The price of buying shares has gone up. The same thing happens in the first equation, which is the same thing as selling the stock at a lower price.Copy the codeTranslate 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;
}
Copy the codeProblem number five. K is equal to 2
K equals 2 is a little bit different than what we did in the previous problem, because it doesn’t depend very much on k. Either k is infinity, the state shift doesn’t matter; Either k = 1, which is close to the base case k = 0, will not exist in the end.
This problem where k is equal to 2 and we’re going to see that k is an arbitrary positive integer, what we do with k comes out. We’ll just write the code and analyze the reasons as we go along.
The original dynamic transfer equation has no simplification 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])
Copy the codeBased on the previous code, we might have assumed that we would write code like this (incorrectly) :
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];
Copy the codeWhy wrong? Didn’t I write it according to the transition equation?
Remember the “exhaust framework” summarized earlier? That means we have to exhaust all the states. In fact, the way we’ve been doing this, we’ve been doing all the states, but we’ve been simplifying all the k’s. Because the influence of k is not eliminated, it is necessary to exhaust k:
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]); }}// select * from max_k;
return dp[n - 1][max_k][0];
Copy the codeIf you don’t understand, you can go back to point 1, “Exhaust frame” and reread it.
PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.
Here, the value range of k is relatively small, so we can not use the for loop, and directly list all the cases where k = 1 and 2.
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;
}
Copy the codeGuided by state transition equations and well-defined variable names, it should be easy for you to follow. Well, we can confuse things by changing these four variables to a, B, C, and D. That way, when people see your code, they’ll freak out and be awestruck.
Number six, k is equal to any integer
Given the fact that k is equal to 2, this should be the same as the first solution. But there is an overmemory error, it turns out that the k value passed in will be very large, the DP array is too large. Now if you think about it, what’s the maximum number of transactions k has?
A trade consists of buying and selling and takes at least two days. So the valid limit k should be no more than n over 2, and if it’s more than that, there’s no constraint, so k is equal to +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];
}
Copy the codeSo far, all six problems have been solved by a state transition equation.
Fourth, the final summary
This article tells us how to solve complex problems through the method of state transfer, using a state transfer equation to kill six stock buying and selling problems in seconds, now think about it, it is not difficult, right? This is already one of the more difficult dynamic programming problems.
The key is to list all the possible “states” and then figure out how to update them. Generally, we store these states in a multidimensional DP array, and we advance backwards from base case to the final state, which is the answer we want. Thinking about this process, do you get a sense of what the term “dynamic programming” means?
Specifically for stock buying and selling, we found three states, using a THREE-DIMENSIONAL array, nothing more than exhaustive + update, but we can say a little more grand, this is called “three-dimensional DP”.
＿＿＿＿＿＿＿＿＿＿＿＿＿
Click on my home page for more quality articles.