Buy and Sell Stock Issues--Deep Mining Dynamic Thinking

admin管理员组

文章数量:1530281

Words written in the front

This is my first English blog，my English is so poor，so I want to use this way to improve my level. Instead of using translation software, I use some words as simple as possible to express my meaning，When I come across some unknown words, I will check them. Some technical terms I will give Chinese Notes. Due to the limited level of English, there are inevitably some grammatical errors. You are welcome to criticize and correct them，Let's feel the charm of thinking in a different way！

Starting from six classic stock problems, this paper digs deeply into dynamic thinking, aiming to understand the essence of dynamic thinking and deal with various dynamic planning problems flexibly.These six stock problems took a few days off and on. The first time to solve these problems, greedy ideas were used. The complexity of time and space was fairly good, but the connections among these ideas were not very well, and they were not suitable for solving a series of problems，In the last stock, we found that the greedy idea could not be applied, so we finally solved it with three-dimensional dynamic planning, of course, the efficiency was not very ideal，Finally, I came across an English problem solution by chance. I connected six problems together, gave a general solution, and thoroughly opened my mind. So I kept thinking about the dynamic core ideas, understood some of them, and shared them here. The original idea of this article was obtained from an English problem solution (I will give a specific link below). I didn't copy this， This is the most original way to explore these problems in a normal way. This article is my exploration process and experience.

Links to the questions I refer to：https://leetcode/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

All the codes in this paper adopt C + +

I'm not good enough. There are some problems in my blog. Welcome to criticize and correct ！

---

0x01.Six stock issues

Question 1：（Only one transaction）

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.

Question 2：（Unlimited number of transactions）

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Question 3:（Freezing period）

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day).

Question 4:（Transaction fee）

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.

Question 5:（Up to two transactions）

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Question 6:（Specified number of transactions）

Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

TIP:All the above questions are from Leetcode Link: In this

---

0x02.Analysis of problems based on dynamic programming

1 – Common character extraction

The above problems seem to have great similarity, and the ultimate demand is the maximum profit obtained. Therefore, these problems must have some common ground.
After analysis, we can get the following commonalities:

• The given array has the same meaning and represents the price on day I.
• The final demand is the same, which is the maximum profit.
• One deal includes buy and sell （This is very important）.
• Buy must be before sell.

2 – Comparison of different properties

The difference between these problems is that we need to analyze the essence of these problems
After analysis, we can get the following differences:

• The maximum number of transactions allowed is different.(The most fundamental difference)
• The status of the transaction is different.(Some need a service charge, some have a freezing period)

3 – Turn multiple questions into one

In order to simplify these problems into one problem, we need to change different properties into the same ones.
How to change different properties into the same can use the dynamic idea. If we set the maximum number of transactions allowed as a variable k, then these problems can be regarded as k The specific problem after the assignment, that is to say, the stock problem with the maximum number of trading allowed as k, is the root problem of these problems. As long as we can solve the root problem, then these sub problems only need to root out the corresponding condition transformation.

4 – The first step of dynamic programming: What is the state?

Now our problem has been transformed into a root problem. After we have determined to use the idea of dynamic planning, the first step we need to think about is: what is the state?
How to understand these States?

• First, see which attributes will affect the results. If they affect the results, they must be considered as states when thinking dynamically.
• Second, when we are in a certain day, what are the choices? Dynamic planning is a process of choosing the best. These choices are the basis of choosing the best.

Now let’s think according to these two ideas:

• An array is given. The content of the array is the stock price of a certain day. Because there is an order between buying and selling, the specific number of days will definitely affect the final result.First status: date.
• here is also an attribute in the question, that is, the maximum number of times allowed to buy or sell. For different times, the result will definitely be different, so we can get ** the second status: the maximum number of times allowed to buy or sell **.
• Then let’s think about what options we have on a specific day. For stocks, we can only have two situations: one is yes, the other is No. on a certain day, you have stocks and no stocks, and the result is definitely different. Therefore, we can get the **third state: position or short position **.

After we determine the state, we can actually write out the corresponding array representation of the state. Three states should correspond to a three-dimensional array:

• DP[i][j][k] // Represents the maximum profit value under the state K in the trading of J times on the I day
• Due to the limited scope of state K, there are only two kinds. We can list them one by one in the form of corresponding flag variables.
• DP[i][j][0] //Represents the maximum profit value when there is no stock in hand on the I-day when j-times trading is allowed at most.
• DP[i][j][1] //It means the maximum profit value when there are stocks in hand on the I-day when j-trades are allowed at most.
• Do not look at it as a three-dimensional array. In fact, the third dimension is equivalent to a flag variable, which can be dimensionally reduced.
• For problems with three states, it’s better to express them in three-dimensional way first, so that they can be understood easily.
• After determining the state expression, we need to find the resultDP[i][k][0] //On the last day, the maximum profit value, which is the answer we need to find, can be bought and sold for up to K times and there is no stock in hand
• The maximum allowed number of transactions j in the array can also be understood as the current j transactions.

There is also a very important problem involved here, that is, when is a transaction completed when is a transaction calculated by buying and selling? Generally, the number of transactions plus 1 is calculated by selling. In this way, in fact, even a transaction can be purchased, but the corresponding meaning of the array needs to be changed.

5 – The second step of dynamic programming: State transfer equation?

After determining the state, we need to determine the state transfer equation, which is also the core content of dynamic planning.
First of all, we need to make sure that this is the problem of finding a maximum value, so when the state is transferred, it should be a process of choosing the best, and how to choose the best is the basis of the transfer equation.

• For DP [i] [j] [0], how is it caused when there is no stock in hand? One situation is that there was no stock before, but I still didn’t buy it on the first day; the other is that there were stocks before, and today they are sold.
• For DP [i] [j] [1], where are the stocks coming from? One situation is that there are stocks on hand because of inaction on the first day; the other is that there are stocks on the first day because there are no stocks.

For each state, there are two choices. We need to find one that can produce the greatest value, that is, a process of choosing the best. How to choose the best? Take the maximum value of the value generated by each option.

• For DP [i] [j] [0], we should choose the maximum value between not buying and selling. If we don’t buy, the value is DP [i-1] [J] [0](that is, the value when there was no stock on the previous day). When buying, the value generated is DP [i-1] [j] [1] + prices [i] (that is, the value of the last day’s stock plus the value of the sale).
• For DP [i] [j] [1], it is the maximum value in choosing not to sell or buy. If not to sell, the value generated is DP [i-1] [j] [1](that is, the value of the stock on the previous day). When buying, the value is DP [i-1] [j-1] [0] - prices [i] (that is, after the j-1 transaction last day, the value of the stock in hand minus the cost of buying the stock).

To sum up, the transfer equation is:

• DP[i][j][0]=max(DP[i-1][j][0],DP[i-1][j][1]+prices[i])
• DP[i][j][1]=max(DP[i-1][j][1],DP[i-1][j-1][0]-prices[i])

6 – The third step of dynamic planning progarmming: Initial conditions?

The first two problems are solved. As long as you find the initial conditions, you can write the code.
When i = 0, we can’t use this equation. Because i= - 1can’t access the array subscript, the cycle we solve must start from 1, so the initial state is the 0 day, that is, i = 0.

The initial conditions are as follows:

• DP[0][j][0]=0 //On the first day, there is no stock in hand. The value is 0
• DP[0][j][1]=-prices[0] //I bought stocks on the first day, but I had no money. Now I owe prices [i]

In addition, there is also a critical condition for j, that is, when j=0, there is no transaction (the actual j is indeed greater than 0, but in the process of circulation, j-1 will occur, so we need to set this value in advance)

• DP[i][0][0]=0 //When trading is not allowed, the value generated without stock is 0
• //When trading is not allowed, it is impossible to hold stocks. The reason for adopting ‘INT_MIN’ is that when taking the maximum value, it directly ignores the value and does not consider its impact

With these three ideas of dynamic progaramming, we have solved this problem. Now, we only need to optimize the following code in specific problems.

7 – How to put the idea of dynamic progaramming into code?

As we mentioned earlier, this is a maximum problem, that is, a process of selecting the best. Because each state may affect the final result, we should fully consider all possible situations, that is, we should traverse all situations, and then choose the best answer in all situations.
To simply look at the root problem, there are three states. In order to traverse all States, it is necessary to triple cycle. Triple cycle can traverse all possible situations. The innermost loops here are 0 and 1, all of which can be done without cycling once.

This three-level loop is just the most basic way to solve the root problem. Of course, in practice, it can be optimized to save unnecessary time and space.

Let’s take a look at the code to solve the root problem: (the initial conditions are also included earlier)

for (int i = 1; i < prices.size(); i++) {
    for (int j = k; j >= 1; j--) {
           DP[i][j][0] = max(DP[i - 1][j][0], DP[i - 1][j][1] + prices[i]);
           DP[i][j][1] = max(DP[i - 1][j][1], DP[i - 1][j - 1][0] - prices[i]);
      }
}
    

---

Next, according to this thought, we can practice it in specific problems

---

0x03.Problem one (Only one transaction)

1 – The case of subproblem in root problem is as follows:

In the first question, we only buy and sell once, which means that the root problem k=1. Because k takes a unique value, we can directly omit this state, all of which are calculated according to the situation of buying and selling once. According to this idea, we can write code.

2 – Write the initial code with the idea of dynamic progaramming:

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

Explain：

• The constant condition of k=1 is omitted here, so the corresponding initialization is also defaulted.
• In the row where dp[i][1] is calculated, the ‘- prices [i]’ should have been
  '0-prices [i]'.

This code is also equivalent to using only one-dimensional array, with space complexity of
O (n) and time complexity of O (n).

But let’s think about it carefully. In each cycle, dp[i][0] and dp[i][1] are only related to
dp[i-1], so we can also optimize this array and use two variables to record the last value.

3 – State compression, simplest code:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 0) return 0;
        int dp0 = 0, dp1 = INT_MIN;
        for (int price:prices) {
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, -price);
        }
        return dp0;
    }
};

Code interpretation：

• dp0actually means dp[i-1][0], that is, it always records the value of the previous time when there was no stock in hand.
• dp1actually means dp[i-1][1], that is, always record the value of the previous stock.

By using variables instead of arrays, the space complexity is reduced to O (1) successfully.
This should be the most ideal plan.

---

When I first solved this problem, I used the greedy thought. For this problem alone, I could get the best answer quickly.

---

0x04.Problem 2 (Unlimited number of transactions)

1 – The case of subproblem in root problem is as follows:

The second problem, which does not limit the number of transactions, shows that ‘k’ can be any value, so we do not need to consider the size of K, which can be directly omitted from the equation of state.

• Note: the omission here is not to consider the impact of transaction times. The omission of the previous problem is the default case of k = 1.

We can write code quickly according to the idea of dynamic progaramming.

2 – Write the initial code with the idea of dynamic progaramming:

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

Observe the code of this problem and the previous one, and you will know that the meaning of omission is totally different!

Similarly, the dp array here can be optimized.

3 – State compression, simplest code:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp0 = 0, dp1 = INT_MIN, temp;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, temp - price);
        }
        return dp0;
    }
};

Code interpretation：

• Here, the meaning of temp is to record the value of the last dp [i-1] [0]. If you use it directly, it will be the changed value.

---

This problem can also be solved quickly by greedy thinking, and it is very easy to understand.

---

0x05.Problem 3 and 4 (Including freezing period and handling fee)

1 – The case of subproblem in root problem is as follows:

As like as two peas, three, four are essentially the same as problem two, but only add some restrictive factors. These constraints do not need to be discussed as a state alone.

• The freezing period of question 3 is that every time we sell, we need to buy every other day, but there is no restriction on selling. According to this condition, we only need to change the calculation expression of dp1 to dp1 = max (dp1, dp0pre price) on the basis of question 2, in which dp0pre means the value when there is no stock in hand in the previous two days, which is equal to the realization of buying every other day after selling.
• The handling fee of question 4 will be better handled. Only on the basis of question 2, each time you buy, you need to deduct the handling fee.
• The rest of the details are the same as question 2.

2 – Final resolution code:

Problem 3:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp0 = 0, dp1 = INT_MIN, temp, dp0pre = 0;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, dp0pre - price);
            dp0pre = temp;
        }
        return dp0;
    }
};

Problem 4:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int dp0 = 0, dp1 = INT_MIN, temp;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, temp - price - fee);
        }
        return dp0;
    }
};

---

These two problems can also be solved by greedy thinking

---

0x06.Problem 5（Up to two transactions）

1 – The case of subproblem in root problem is as follows:

In fact, problem 5 is in the case of k = 2. At this time, because k can take multiple values, we can’t simply omit the value of k like the problem, but we need to traverse the state of k and choose the best solution.

2 – Write the initial code with the idea of dynamic progaramming:

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

The code should not need to be explained too much, that is, the code form of the root problem, but k=2.

But it’s a little complicated to apply the code of root problem directly. We can do some optimization.

At the end of the problem, time complexity is still O（N）.
Optimization ideas:

• When k is 2 , it can be exhausted without using cycles, which reduces one dimension.

• It is found that dp [i] is only related to dp [i-1], so we can compress the state again and change the two-dimensional state into one-dimensional state.

3 – State compression, 3-D to 1-D:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp10, dp11, dp20, dp21;
        dp10 = dp20 = 0;
        dp11 = dp21 = INT_MIN;
        for (int price : prices) {
            dp20 = max(dp20, dp21 + price);
            dp21 = max(dp21, dp10 - price);
            dp10 = max(dp10, dp11 + price);
            dp11 = max(dp11, -price);
        }
        return dp20;
    }
};

Code interpretation：

• dp10 actually represent dp[i][1][0]
• dp11 actually represent dp[i][1][1]
• dp20 actually represent dp[i][2][0]
• dp21 actually represent dp[i][2][1]
• The purpose of taking these four variables is to exhaust all the possibilities of k.
• The method of compression is similar to that of problem 2. Multiple variables can be used to record the previous value.

This method has successfully changed the space complexity to O (1）, which should be the best solution.

---

This problem is difficult to understand in other ways. At first, I solved it in two-dimensional way, the effect is not good.

---

0x07.Problem 6（Specified number of transactions）

This problem can be said to be root problem itself, so with the idea of root problem, I directly tried the following, and had a failed attempt…

Failed attempts – Ignore the efficiency of actual problems

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

The code is correct, but when it is submitted, it exceeds the limit of memory. It can be imagined that this is a three-dimensional array, which is also two-dimensional. When the amount of data is huge, it is easy to exceed the limit of memory.

So if we want to find a way to reduce dimensions, the first idea is that dp [i] is only related to
dp [i-1], so it can definitely reduce one dimension.
So using the idea of dimension reduction, write the code quickly.

Attempts to reduce dimensions:

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

In this way, one dimension has been successfully reduced. The whole idea of reducing the dimension is similar to that of question 2, but this is to specify k.

When I try again, I find that the memory limit is still exceeded. Should I continue to reduce it??
So I looked at the test data and found that k = 1000000000, which is a billion . There must not be so much data behind it, so I should ignore the value range of k.

• First of all, k must not exceed n. Otherwise, it would be meaningless. But is it really more than n?
• At least two days are needed for a transaction. If k > = n / 2, it has lost the meaning of restriction. That is to say, it is the same as problem 2, so there is no need to create a two-dimensional array specifically. You can use the method of problem 2 to solve it.

With this idea, we can write detailed code.

Combined problem solving:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0.;
        if (k >= n / 2) {
            int dp0 = 0, dp1 = INT_MIN, temp;
            for (int price : prices) {
                temp = dp0;
                dp0 = max(dp0, dp1 + price);
                dp1 = max(dp1, temp - price);
            }
            return dp0;
        }
        vector<vector<int>> dp(k + 1, vector<int>{0, INT_MIN});
        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }
};

In the end, it solved the problem perfectly.

In fact, there is still a one-dimensional solution, which is to use two one-dimensional arrays for processing, but this method has some deviation from our main idea, so it is not listed here.

Handling of details:

• When traversing, there is a problem about the direction of inner layer traversal. In fact, both methods can be used. The proof process will not be given here.
• Some methods are initialized, while others are not. The root cause is whether the i level is optimized. If it is optimized, some are unnecessary.

So far, all the problems have been solved perfectly.

0x08.Summary – Deep mining dynamic thought

In the analysis of multiple problems, we try to find their root problem, then solve the root problem, and finally optimize the code according to the actual situation. This process is a dynamic process.

The idea of dynamic programming is used to analyze several problems:

• Common character extraction
• Comparison of different properties
• Turn multiple questions into one
• Look for status, look for all attributes that may have an impact on the results
• The process of finding transfer equation and selecting the best
• Find the transfer equation, find the initial conditions in the process of selecting the best, and solve the root of the problem
• Traverse all States to find the best solution
• Optimize unnecessary states for specific problems
• State compression to solve problems in the most efficient way

The essence of dynamic programming idea:

• The essence of dynamic programming is a process of constantly choosing the best. Or it is a process of accumulation.
• How to choose the best has become the key to our problem.
• Traversal of all possible cases is the basis of selection.

How to understand the dynamic process?

• The dynamic process is the static continuous transformation and iteration.
• Dynamic means that all States are dynamic.
• Planning is how to make them move in our hands.

In a word, the solution of all dynamic programming problems is summarized:

Traverse all attributes to find the best solution

So far, this blog has ended. This blog takes a long time. It aims to dig out the essence and core idea of dynamic planning through this series of small problems, so as to avoid panic when encountering dynamic planning problems in the future. I hope my article can help you, that's all.

ATFWUS --Writing By 2020–03–10 to 2020–03–18
End in 2020–03–18

!

本文标签： StockIssuesBuySelldynamic