[Dynamic programming] The best date to buy and sell stocks, dynamic programming, greedy + dynamic programming, dynamic programming

The article directories

• • • Leetcode121 The best date to buy and sell stocks ① Dynamic programming
    • • Topic describes
      • Dp [I]= Max (dp[I −1],prices[I]−minprice)
    • Leetcode122 The best date to buy and sell stocks ② Greedy + dynamic programming
    • • Topic describes
      • Solution 1: Greed, eat up all the rise, must be the biggest, even the rise is covered by greed
      • Solution 2: Dynamic programming
    • Leetcode123 the best time to buy and sell stocks ③ dynamic planning
    • • Topic describes
      • Solution: dynamic programming

Leetcode121 The best date to buy and sell stocks ① Dynamic programming

Max (dp[i-1],prices[I] -minprice); Initialize dp[0]=0 dp[1]=0 dp[2] to start performing the characteristic equation

Topic describes

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
Copy the code

Dp [I]= Max (dp[I −1],prices[I]−minprice)

Dynamic programming is generally divided into one-dimensional, two-dimensional and multidimensional (using state compression), and the corresponding forms are DP (I) DP (I), DP (I)(j) DP (I)(j), and binary DP (I)(j) binary DP (I)(j).

1. Specify what dp(I)dp(I) should represent (two-dimensional case: dp(I)(j)dp(I)(j));
2. According to the relationship between DP (I) DP (I) and DP (i-1) DP (I −1), the state transition equation is obtained.
3. Determine initial conditions, such as dp(0), dp(0).

Dp [I] = Max (dp [I – 1), prices [I] – minprice)

Thoroughly understand this dp characteristic equation:

1. Dp [I] represents the maximum profit on day I;
2. Dp [i-1] indicates the same status as on the previous day, no stocks are currently held, so no stocks were held on the previous day, so the same as on the previous day. Note: On day I, there are two possibilities for not owning a stock: waiting for the stock you have not yet bought, or selling the stock you have bought.
3. Prices [I]− Minprice Indicates shares currently owned and can be sold at today’s prices, having been bought at the lowest price.

In both cases, let’s take the maximum.

If you can only buy once, you can only have two states on day I. If you do not hold stocks on day I, then you must not hold stocks on day I-1, and the profits are the same as on day I-1 (you may have completed the buying and selling operation, but may not have started the buying and selling operation). On day I, if you own a stock, you can sell it at today’s price, if you bought it at the lowest price. In this dynamic programming equation, we’re taking both cases into account, so that’s fine.

class Solution {
    public int maxProfit(int[] prices) {
       if(prices.length==0) return 0;
       int minPrice=prices[0];
       int dp[]=new int[prices.length];
       for(int i=1; i<prices.length; i++){ minPrice=Math.min(minPrice,prices[i]); dp[i]=Math.max(dp[i-1],prices[i]-minPrice); }returndp[prices.length-1]; }}Copy the code

Because dp[I] is only related to dp[i-1], it is directly simplified by replacing dp array with maxProfit, as follows:

class Solution {
    public int maxProfit(int[] prices) {
       if(prices.length==0) return 0;
       int minPrice=prices[0];
       int maxProfit=0;
       for(int i=1; i<prices.length; i++){ minPrice=Math.min(minPrice,prices[i]); maxProfit=Math.max(maxProfit,prices[i]-minPrice); }returnmaxProfit; }}Copy the code

In fact, for this dynamic programming equation, if you want to see it more clearly, you can write it in two dimensions, plus the judgment of whether you currently hold stocks, as follows:

Leetcode122 The best date to buy and sell stocks ② Greedy + dynamic programming

Topic describes

Title description:

Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1: Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.

Example 2: Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can’t buy stocks on day 1 and day 2 and then sell them later. Because you’re doing multiple trades at once, you have to sell your shares before you can buy them again.

Example 3: input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

1 <= prices. Length <= 3 * 10 ^ 4 0 <= prices[I] <= 10 ^ 4

Solution 1: Greed, eat up all the rise, must be the biggest, even the rise is covered by greed

class Solution {
    public int maxProfit(int[] prices) {
       if(prices.length<2)
            return  0;
        int value=0;
       
        for(int i=1; i<prices.length; I++) {// eat up all the gains in volatile markets and avoid all the declinesif(prices[i]>prices[i-1])  
                value+=prices[i]-prices[i-1];
        }
        returnvalue; }}Copy the code

Solution 2: Dynamic programming

Considering that “you can’t participate in more than one transaction at the same time”, there are only two possible options after the trading ends on day I:

1. I have a stock dp[I][1]
2. State without stock dp[I][0]

You can’t own two stocks.

Definition state DP [I][0] represents the maximum profit without stock in hand after trading on day I, and DP [I][1] represents the maximum profit with one stock in hand after trading on day I (I starts from 0).

Consider the transfer equation of DP [I][0], indicating that there are no shares in hand after trading on that day:

1. There may be no stock on the previous day, that is, DP [I −1][0], which means to continue waiting.
2. Holding a stock at the end of the previous day, called DP [I −1][1], means selling the stock and making a profit on prices[I].

Therefore, in order to maximize returns, we listed the following transfer equation:

Dp [I] [0] = Max {dp [0], [I – 1] dp [I – 1) + prices [1] [I]}

This dynamic programming equation represents the maximum profit of the two situations on the previous day when there were no stocks.

Then consider dp[I][1], and consider the transfer state in the same way, then the possible transfer state is

1. The previous day has held a stock, that is, DP [I −1][1], indicating continued holding;
2. There are no shares at the end of the previous day, that is, DP [I −1][0], which means buying shares and reducing the principal of prices[I].

The transfer equation can be listed as follows:

Dp [I] [1] = Max {dp [1], [I – 1] dp [I – 1] [0] – prices [I]}

This dynamic programming equation represents the maximum profit of the two situations on the day before the stock is currently held.

Prices [I] +prices[I] +prices[I] +prices[I] +prices[I] To hold or not to hold the stock is dp[i-1][0 or 1].

For the initial state, according to the state definition, dp[0][0] = 0 and DP [0][1] = −prices[0] when the transaction ends on day 0.

So we can just compute the states from front to back. Since the return on holding the stock must be lower than the return on not holding the stock after all trading is completed (because the stock is sold to make money, you can also make a final comparison by taking the larger of dp[n−1][0] and DP [n−1][1]), the final answer is DP [n−1][0].

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][2]; dp[0][0] = 0; Dp [0][1] = -prices[0]; // Initialize: buy the stock on day 0 and the yield is -prices[0], or the principal in hand is -prices[0]for (int i = 1; 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], dp[i - 1][0] - prices[i]);
        }
        returndp[n - 1][0]; }}Copy the code

Note that in the state transition equation above, each day’s state is only related to the previous day’s state, and not to the earlier state, so we don’t need to store these irrelevant states, just store DP [I −1][0] and DP [I −1][1] in two variables, Through them, dp[I][0] and DP [I][1] can be calculated and returned to the corresponding variables, so as to facilitate the state transfer on day I +1.

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int dp0 = 0, dp1 = -prices[0];
        for (int i = 1; i < n; ++i) {
            int newDp0 = Math.max(dp0, dp1 + prices[i]);
            int newDp1 = Math.max(dp1, dp0 - prices[i]);
            dp0 = newDp0;
            dp1 = newDp1;
        }
        returndp0; }}Copy the code

Leetcode123 the best time to buy and sell stocks ③ dynamic planning

Topic describes

Given an array, its ith element is the price of a given stock on day I. Design an algorithm to calculate the maximum profit you can make. You can make up to two deals. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), the transaction will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit of 4-1 = 3.

Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can’t buy stocks on day 1 and day 2 and then sell them later. Because you’re doing multiple trades at once, you have to sell your shares before you can buy them again.

Example 3: input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

1 <= prices. Length <= 10^5 0 <= prices[I] <= 10^5

Solution: dynamic programming

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); 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]);
        }
        returndp[prices.size() - 1][4]; }};Copy the code

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

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        returnsell2; }}Copy the code