Writing in the front

If you feel that the writing is good, some harvest, remember to click attention and click a like yo, thank you very much. This series of stock trading issues was previously covered in LeetCode, but for some reason it was not summarized in a blog post. After again and again encountered similar problems, always feel that the stock series of problems of strange technology is too much, usually used to learn and expand completely is no problem, but if to some formal occasions, generally do not think of those clever ways, how to do? So this blog post is going to be slow and steady, through a more detailed explanation, with a general approach to solve the problem, so as not to change.

The article directories

Introduction of related issues

Stock trading issues have been a plite issue, but in accordance with normal logic, or to explain the problem, otherwise it may be not friendly for some readers who do not know, so here will be the relevant problem address posted, will not describe the problem in the blog, as follows:

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 including the freeze period including the fees

It’s worth noting that for each problem, there are some excellent articles explaining how to solve the corresponding problem. However, most solutions fail to establish a connection between these questions, making it difficult to find a consistent way to deal with this set of questions. In this blog post, I’ll introduce the most common solutions that apply to all of these problems and specialize them into each of the six above.

This article will through the state machine to explain, many people may heard the state machine, the heart of fear, and think it is a distant thing, actually don’t have to think how tall, is in fact DP table, waiting for you to understand the you can see, I thought behind wrote an article for the state machine’s thinking some unique usage, Because there are some problems that can be solved perfectly with a state machine. Before we start, let’s take a look at some code

int maxProfit(vector<int>& prices) {
    if(prices.empty()) return 0;
    int s1=-prices[0],s2=INT_MIN,s3=INT_MIN,s4=INT_MIN;
        
    for(int i=1; i<prices.size(); ++i) { s1 = max(s1, -prices[i]); s2 = max(s2, s1+prices[i]); s3 = max(s3, s2-prices[i]); s4 = max(s4, s3+prices[i]); }return max(0,s4);
}
Copy the code

This code is minimal and seems to take only a few minutes to read, but in many cases, the more concise the code, the more mysterious it is, and worth digging into. Of course, the above code is the code to solve one of the stock problems, it is very simple, but if you think you have understood the meaning of the code to solve all the stock problems, you can try to write the above six problems yourself, I am sure you will come back. If you haven’t floated yet, keep reading. While other people may doubt themselves that they can write such super-compact code all at once, there is a framework for this kind of problem, and once you understand the framework, you can write the same code. So here is to say a topic, that is, if you are still very vegetables, brush more questions, read more, more research, after the routine is clear, you do not understand the routine in front of the small white, is the big guy.

Back to the point, these six stock trading problems are common, we solve them one by one through the analysis of the fourth question (limit maximum trading times for K). Since question 4 is the most general form, all the other questions are simplifications or derivations of this form. 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.

What is the understanding state

First, we’re going to do something simple and violent, which is brute force, but by brute force, we’re not going to do brute force like recursion or ordinary multilevel traversal, where we’re going to do brute force on all the buy and sell combinations. Let’s do something different, something different. Here, all of our units’ buying and selling portfolios are exhausted, but each day’s “state” is exhausted. It may be difficult to understand, but to be more specific, we look at each day, see how many possible “states” there are, and then find the “choices” corresponding to 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. Let’s simplify the code for this idea, as follows:

forstate1In the state1All values of:forstate2In the state2All values of:for. Dp [state1] [state2] [...]. = Choose the best1, the choice of2...)
Copy the code

For 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’s very complicated, right? Don’t be afraid, what we’re going to do is just enumish, no matter how many states it has, what we’re going to do is we’re going to enumish them all in one 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 code

In 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. 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. At this point you 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. At this point, you need to remember how to interpret “states”, and once you find something difficult to understand, it will be easier to translate into natural language.

State transition framework

Now, we’re done"State"We began to think about each"State"What are the"Choice"How should it be updated"State". Just look at"Holding state"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[I]) I don't own shares today. There are two possibilities: either I didn't own shares yesterday and then I choose REST today, so I still don't own shares 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[I]) Today I own stocks. There are two possibilities: either I own stocks yesterday and then I choose REST today, so I still own stocks today; Or I didn't own the stock yesterday, but today I choose buy, so I own the stock today.Copy the code

The 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 should be able to solve all the problems in a second, just use this framework. But there’s a little bit left to do, which is to define the base case, the simplest case.

dp[-1][k][0] = 0Explanation: Because I is from0I started, so I is equal to minus1That means we haven't started yet, so the profit at this point is of course0. 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] = 0Explanation: because K is from1I started, so k is equal to0It means you're not allowed to trade at all, and of course the profit is0. dp[i][0] [1] = -infinity explanation: It is impossible to own a stock without being allowed to trade, denoted by negative infinity.Copy the code

To summarize the state transition equation above:

base case: [- dp1][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])
Copy the code

So at this point you might say, well, 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.

Combat problem solving

When only one transaction can be made

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]0The base ofcaseSo dp [I -1] [0] [0] = 0. Now we find that k is both1, will not change, that is, k has no effect on the state transition. This 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])
Copy the code

The code is as follows:

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 code

Obviously 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 code

The 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):

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 code

Both 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.

When you can make an infinite number of trades

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 code

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;
}
Copy the code

When you can trade an infinite number of times, and limit the suspension of trading

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[i-1] [0], dp[i-1] [1] + prices[i])
dp[i][1] = max(dp[i-1] [1], dp[i-2] [0] -prices [I]) 错 误 : Select buy from I -2State transition, not I -1 。
Copy the code

Translated 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 code

When you can make an infinite number of transactions and you have to pay a fee

Each transaction pays a fee, which can be subtracted 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[I] -price [I] -fee) The same thing happens in the first equation, which is the same thing as selling the stock at a lower price.Copy the code

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;
}
Copy the code

When you can make two trades

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 code

Based 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) { /* Handle base case*/ }
    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 code

Why 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) { /* Handle base case */ }
        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 code

If you don’t understand, you can go back to point 1, “Exhaust frame” and reread it. Here, the value range of k is relatively small, so it is possible to manually list k = 1 and 2 without using the for loop:

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 code

Guided 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. So when people see your code, they will be confused and frightened and have to respect you.

When you can make any transaction

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) { /* Handle base case */ }
            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 code