Have you ever seen this kind of dynamic programming -- the stock problem of state machine dynamic programming (Part 2)

Preface

In the first two articles Have you ever seen this kind of Dynamic Planning —— Stock problem of state machine dynamic programming ( On ) and Have you ever seen this kind of Dynamic Planning —— Stock problem of state machine dynamic programming ( in ) Already talked 4 Tao and stock related issues , Explained in detail State machine dynamic programming And his basic principles and application methods . In this article , I will introduce the remaining two stock issues , Continue to deepen and learn State machine dynamic programming .

The best time to buy and sell stocks includes the freezing period

subject

Given an array of integers prices, Among them the first prices[i] It means the first one i Day's share price .

Design an algorithm to calculate the maximum profit . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）: After sale of shares , You can't buy shares the next day ( That is, the freezing period is 1 God ).

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

Example

Example 1:

 Input : prices = [1,2,3,0,2]
 Output : 3 
 explain :  The corresponding transaction status is : [ purchase ,  sell ,  Freezing period ,  purchase ,  sell ]

Example 2:

 Input : prices = [1]
 Output : 0

State representation array and state transition equation

Like the previous topic, first of all, we need to define the state and analyze the state transition , In this problem, we use a two-dimensional array dp[i][j] It represents the benefits under various states , In this problem, we have the following states ：

• dp[i][0], Indicates that you are traversing to the i There is no buying or selling of stocks .

  • At this time, there is no buying or selling , At this time, the income and traversal reach the i-1 The situation of not buying and selling stocks is the same , Their income is equal to 0, namely dp[i][0] = 0,dp[i - 1][0] = 0.

• dp[i][1], Indicates that you are traversing to the i When you buy stocks, you have stocks in your hands , This situation can be explained by 3、 ... and The situation shifts ：

  • After traversing to the i-1 When you buy stocks, you already have stocks in your hands , At this time, you just need to keep in shape , Then in the first place i The return when buying stocks and the i-1 The returns of each stock are equal , namely dp[i][1] = dp[i - 1][1].
  • The second case is to traverse to the i-1 There is no stock in your hand when you buy a stock , At this time, if you want to have stocks in your hands, you need to buy , Then it will cost prices[i], So when we traverse to the i When you buy a stock, the return is equal to dp[i][1] = dp[i - 1][0] - prices[i].
  • The third situation is that the previous day was in the freezing period （ The freezing period mentioned here is not just before 2 Day sell , Resulting in the freezing period of the previous day , It may have been sold earlier , Then keep it in its state , It is equivalent to the renewal of the freezing period , But you can buy stocks during the renewal ）, Now you can buy , namely dp[i][1] = dp[i - 1][3] - prices[i], among dp[i][3] Indicates traversing to the i Earnings in the frozen period when stocks are paid .
  • Combining the above three situations ：

  $$dp[i][1]=max(dp[i-1][1],max(dp[i-1][0]-prices[i],dp[i-1][3]-prices[i]))$$

• dp[i][2], Said in the first i There are no stocks in your hand when you buy stocks , There are two states that can be transferred to this state ：

  • After traversing to the i-1 When you buy stocks, there are no stocks in your hands , Then we just need to stay in shape , namely dp[i][2] = dp[i - 1][2].
  • After traversing to the i-1 When you buy stocks, you have stocks in your hands , Then we need to sell this stock , namely dp[i][2] = dp[i - 1][1] + prices[i].
  • Combining the above two situations ：

  $$dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])$$

• dp[i][3], Said in the first i Stocks are in the freezing period , This state can only be transferred from one state , That is, there was no stock in hand the day before （ Because I sold ）, namely dp[i][3] = dp[i][2].

Initialization and traversal order of array

According to the above analysis, we can know , When traversing the first stock, if you hold the stock, you need to buy , Then the status of buying dp[0][1] The value of is equal to -prices[0], The status income of selling is 0, The state of freezing period is also equal to 0. According to the state transition equation, section i The data of the row depends on i-1 That's ok , So traverse from front to back .

The biggest gain

According to the status we set above , The biggest benefit we can get is dp[prices.length - 1][2], dp[prices.length - 1][3] One of the two , Because in the end, if we want to gain the most, there must be no stocks in our hands , There are two states mentioned above when there is no stock .
$$max(dp[prices.length-1][2],dp[prices.length-1][3])$$

Code

class Solution {
    
  public int maxProfit(int[] prices) {
    
    // dp[i][0]  It means that there is no buying or selling operation   This value is always equal to 0, You can not use this state 
    //  But in order to be complete, this state is left 
    // dp[i][1]  To hold shares 
    // dp[i][2]  Indicates that you do not hold shares 
    // dp[i][3]  The freezing period after the selling operation 
    int[][] dp = new int[prices.length][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]),
          dp[i][0] - prices[i]); //  because dp[i][0]  Always equal to 0  So it can be written directly here  -prices[i]  It's OK 
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
      dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]);
  }
}

because dp[i][0] Always equal to 0, So let's include dp[i][0] Can be deleted , So the following code is also correct .

class Solution {
    
  public int maxProfit(int[] prices) {
    
    // dp[i][0]  It means that there is no buying or selling operation   This value is always equal to 0, You can not use this state 
    //  But in order to be complete, this state is left 
    // dp[i][1]  To hold shares 
    // dp[i][2]  Indicates that you do not hold shares 
    // dp[i][3]  The freezing period after the selling operation 
    int[][] dp = new int[prices.length][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]),
          -prices[i]); 
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
      dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]);
  }
}

Array optimization —— Scrolling array

In the above state transition equation, we always use only two lines of data , So we can only use a two-dimensional array , Then use it alternately （ Yes i seek 2 The remainder of is enough ） That's all right. , The code is as follows ：

class Solution {
    
  public int maxProfit(int[] prices) {
    
    int[][] dp = new int[2][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[i & 1][1] = Math.max(Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][3] - prices[i]),
          dp[i & 1][0] - prices[i]);
      dp[i & 1][2] = Math.max(dp[(i - 1) & 1][2], dp[(i - 1) & 1][1] + prices[i]);
      dp[i & 1][3] = dp[(i - 1) & 1][2];
    }
    return Math.max(dp[(prices.length - 1) & 1][2], dp[(prices.length - 1) & 1][3]);
  }
}

The best time to buy and sell stocks includes handling fees

subject

Given an array of integers prices, among prices[i] It means the first one i Day's share price ; Integers fee Represents the handling fee for trading shares .

You can close the deal indefinitely , But you have to pay a handling fee for every transaction . If you have bought a stock , You can't buy any more stock until you sell it .

Return the maximum profit .

Be careful ： A deal here refers to the whole process of buying, holding and selling stocks , You only need to pay a handling fee for each transaction .

Example

Example 1

 Input ：prices = [1, 3, 2, 8, 4, 9], fee = 2
 Output ：8
 explain ： The maximum profit that can be achieved :  
 Buy... Here  prices[0] = 1
 Sell... Here  prices[3] = 8
 Buy... Here  prices[4] = 4
 Sell... Here  prices[5] = 9
 Total profit : ((8 - 1) - 2) + ((9 - 4) - 2) = 8

Example 2

 Input ：prices = [1,3,7,5,10,3], fee = 3
 Output ：6

State representation array and state transition equation

This question is actually in Have you ever seen this kind of Dynamic Planning —— Stock problem of state machine dynamic programming ( On ) The second question is very similar , The only difference is that there is a handling fee , The rest is exactly the same .

Now let's analyze how to transfer the state ：

• dp[i][0] How is the state of i-1 The state of the world has changed ：

  • If the first i-1 One state is that there is no stock in hand , namely dp[i-1][0], So the first i There are no stocks in each state , So directly dp[i][0] = dp[i - 1][0], Because there is no transaction .
  • If the first i-1 There are stocks in the hands of States , namely dp[i-1][1], So if you want to i There are no stocks in this state , Then you need to sell the stock , Then the income is dp[i-1][1] + prices[i], namely dp[i][0] = dp[i-1][1] + prices[i], But there will be a handling charge in this topic , We need to pay a handling fee when we sell , Then our income becomes dp[i][0] = dp[i-1][1] + prices[i] -fee.
  • Combining the above two transfer methods, we can get the following transfer equation ：

  $$dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)$$

• dp[i][1] How to transfer the state of ：

  • If the first i-1 One state is that there is no stock in hand , namely dp[i-1][0], Then we need to start from i-1 Buy when there are no stocks in your hands , that dp[i][0] = dp[i - 1][0] - prices[i].
  • If the first i-1 There are stocks in the hands of States , namely dp[i-1][1], And the first i There are stocks in three states , So there is no need to trade , namely dp[i][1]=dp[i - 1][1].
  • Combining the above two transfer methods, we can get the following transfer equation ：

  $$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);$$

• Combine the above two states ：

$$\{\begin{array}{l}dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)\\ dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);\end{array}$$

Code

class Solution {
    
  public int maxProfit(int[] prices, int fee) {
    
    int[][] dp = new int[prices.length][2];
    // dp[i][0]  Indicates that you do not hold shares 
    // dp[i][1]  To hold shares 
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
      dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[prices.length - 1][0];
  }
}

Array optimization —— Scrolling array

class Solution {
    
  public int maxProfit(int[] prices, int fee) {
    
    int[][] dp = new int[2][2];
    // dp[i][0]  Indicates that you do not hold shares 
    // dp[i][1]  To hold shares 
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i] - fee);
      dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
    }
    return dp[(prices.length - 1) & 1][0];
  }
}

To optimize the

class Solution {
    
  public int maxProfit(int[] prices, int fee) {
    
    int[] dp = new int[2];
    // dp[0]  Indicates that you do not hold shares 
    // dp[1]  To hold shares 
    dp[1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
    
      dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    }
    return dp[0];
  }
}

The above code optimization and Have you ever seen this kind of Dynamic Planning —— Stock problem of state machine dynamic programming ( in ) The optimization principle is the same . In the following code , The single row array on the left dp[0] and dp[1] It is equivalent to dp[i][0],dp[i][1], The single row array on the right dp[0] and dp[1] Equivalent to a two-dimensional array dp[i - 1][0] and dp[i - 1][1].

dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
dp[1] = Math.max(dp[1], dp[0] - prices[i]);

But we will find that the second line of the above code depends on dp[0], This dp[0] It's No i-1 The state of the line , however dp[0] An update has occurred in the first line , in other words dp[0] Has been updated to page i The state of the line , So why is the result right ？ We can analyze according to the following three rules ：

• If dp[0] What is taken is dp[0], in other words dp[0] > dp[1] + prices[i] - fee , that dp[0] Or the status of the previous line , Does not affect dp[1] Result .
• If dp[0] What is taken is dp[1] + prices[i] - fee, however dp[1] It's from the previous line dp[1] Then it has no effect on the result .
• If dp[0] What is taken is dp[1] + prices[i] - fee and dp[1] What is taken is dp[0] - prices[i], Then it will have an impact , But this plus and minus is actually meaningless , You simply need to pay a handling fee , Final dp[0] - prices[i] = dp[1] + prices[i] - fee - prices[i] = dp[1] - fee < dp[1] , Therefore, this state will not be taken by the final result , The state taken must be the first i-1 Yes dp[1]（ because dp[1] Bigger ）, In other words, this state will shift to the second , Therefore, it has no effect on the final result .

summary

In this article, I mainly introduce the last two stock issues , The state transition of the first question is still relatively complex , You may need to experience it carefully , Can understand , In particular, the transformation of the state during the freezing period may be more convoluted . The second topic in this article is very similar to the previous topic , Just subtract the handling fee from the income . I believe after reading these three articles , After finishing these six questions, you are right State machine dynamic programming The basic principle of has been well understood , The most difference between it and traditional dynamic programming is that there are many complex transitions between States , And the general topic of dynamic programming is multiple cycles , But in State machine dynamic programming There is a single cycle .

---

More wonderful content collections can be accessed to the project ：https://github.com/Chang-LeHung/CSCore

Official account ： Worthless research monk , Learn more about computers （Java、Python、 Fundamentals of computer system 、 Algorithm and data structure ） knowledge .