Dynamic programming to solve stock problems (Part 2)

Dynamic programming solves the stock problem （ Next ）

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

Title Description

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

Force link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown

Answer key

We use it dp[i] It means the first one i At the end of the day 「 Cumulative maximum return 」. According to the title , Because we can only buy at the same time （ hold ） A stock , And there is a freeze period after selling shares , So we have three different states ：

• We currently hold a stock , Corresponding Cumulative maximum return Write it down as dp[i][0];
• We do not currently hold any shares , And in the freezing period , Corresponding Cumulative maximum return Write it down as f[i][1];
• We do not currently hold any shares , And not in the freezing period , Corresponding Cumulative maximum return Write it down as f[i][2].

How to make state transition ？ In the i days , We can do it without breaking the rules purchase perhaps sell operation , At this time i The state of the day will change from i−1 The state of heaven shifts ; We can also do nothing , At this time i The state of the day is equivalent to the i−1 The state of heaven . So let's analyze these three states respectively ：

about dp[i][0], The stock we currently hold can be in the i−1 Days already hold , The corresponding state is f[i−1][0]; Or no i Days bought , So the first i-1 You can't hold stocks for days and are not in the freezing period , The corresponding state is dp[i−1][2] Plus the negative return on buying stocks prices[i]. So the state transfer equation is ：dp[i][0]=max(dp[i−1][0], dp[i−1][2]−prices[i])

about dp[i][1], We are the first i The reason why it is in the freezing period after the end of the day is that it sold shares on the same day , Then explain in the second i−1 One day we have to hold a stock , The corresponding state is dp[i−1][0] Plus the positive return on selling shares prices[i]. So the state transfer equation is ：dp[i][1]=dp[i−1][0]+prices[i]

about dp[i][2], We are the first i Do not hold any shares after the end of the day and are not in the freezing period , It means that no operation was carried out on that day , That is to say i-1 Tianshi doesn't hold any shares ： If it's frozen , The corresponding state is dp[i−1][1]; If it's not frozen , The corresponding state is dp[i−1][2]. So the state transfer equation is ：dp[i][2]=max(dp[i−1][1],dp[i−1][2])

So we get all the state transfer equations . If there is n God , Then the final answer is ：max(dp[n−1][0],dp[n−1][1],dp[n−1][2])

Notice if on the last day （ The first n−1 God ） After that , Still holding shares , Then obviously it doesn't make any sense . So more precisely , The final answer is actually dp[n-1][1] and dp[n-1][2] The greater of , namely ：max(dp[n−1][1],dp[n−1][2])

Notice that in the state transfer equation above ,dp[i][..] Only with dp[i-1][..] of , And with the dp[i-2][..] It has nothing to do with all previous states , So we don't have to store these irrelevant States . in other words , We just need to put dp[i-1][0],dp[i−1][1],dp[i-1][2] Stored in three variables , They calculate dp[i][0],dp[i][1],dp[i][2] Coexist back to the corresponding variable , So that the second i+1 The state of days can be transferred .

/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    
  const length = prices.length;
  let [dp0, dp1, dp2] = [-prices[0], 0, 0];

  for(let i = 1; i < length; i++) {
    
    let newDp0 = Math.max(dp0, dp1 - prices[i]);
    let newDp1 = Math.max(dp1, dp2);
    let newDp2 = dp0 + prices[i];
    dp0 = newDp0;
    dp1 = newDp1;
    dp2 = newDp2;
  }

  return Math.max(dp1, dp2);
};

2. The best time to buy and sell stocks III

Title Description

Given an array , It's the first i An element is a given stock in the i Sky price .
Design an algorithm to calculate the maximum profit you can get . You can do at most   Two pens   transaction .
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  1:

 Input ：prices = [3,3,5,0,0,3,1,4]
 Output ：6
 explain ： In the  4  God （ Stock price  = 0） Buy when , In the  6  God （ Stock price  = 3） Sell when , The exchange will make a profit  = 3-0 = 3 .
      And then , In the  7  God （ Stock price  = 1） Buy when , In the  8  God  （ Stock price  = 4） Sell when , The exchange will make a profit  = 4-1 = 3 .

Example 2：

 Input ：prices = [1,2,3,4,5]
 Output ：4
 explain ： In the  1  God （ Stock price  = 1） Buy when , In the  5  God  （ Stock price  = 5） Sell when ,  The exchange will make a profit  = 5-1 = 4 .   
      Notice that you can't be in the  1  Day and day  2  Day after day buying stock , Then sell them .   
      Because it's involved in multiple transactions at the same time , You have to sell the stock before you buy it again .

Example 3：

 Input ：prices = [7,6,4,3,1] 
 Output ：0 
 explain ： In this case ,  No deal is done ,  So the biggest profit is  0.

Example 4：

 Input ：prices = [1]
 Output ：0

Force link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

Answer key

At the end of each day , It may be in the following Five states One of ：

1. Neither buying nor selling shares .
2. Bought the first stock , But I haven't sold the first stock yet .
3. Bought the first stock , And sell the first stock .
4. Bought the first stock , And sell the first stock , Bought a second share , But I haven't sold the second stock yet .
5. Bought the first stock , And sell the first stock , Bought a second share , And sell the second stock .

We can traverse prices Array , Simulation No i The situation of the day . Calculate the second i The maximum value of profit in five cases .

• For the first case , Profit is always 0.
• For the second case , Because there is no profit yet , Only bought a certain stock , In the state of loss . here , The minimum loss is prices[0] to prices[i] The minimum value of , Assuming that buy1. Can be seen as , In the second case, the maximum profit is ：-buy1. The equation of state transfer is ：buy1 = max(buy1, -prices[i]);
• For the third case , The calculation of profit requires selling another share on the basis of the second case . So we need to calculate the second case first , Then traverse to prices[i] When , Decide whether to sell . If you buy the first stock with the smallest loss , The biggest profit from selling the current stock , Then sell the current stock . The equation of state transfer is ：sell1 = max(sell1, prices[i] + buy1); Notice that this is prices[i] + buy1, No prices[i] - buy1, because buy1 It's negative , For profit .
• For the fourth case , You can't buy directly , Because it's possible that the first stock hasn't been sold yet . The calculation of profit needs to buy another stock on the basis of the third case . So we need to calculate the third case first , Then traverse to prices[i] When , Decide whether to buy . If the profit from selling the first share is the largest , The ultimate profit from buying the current stock is the largest , Then buy the current stock . The equation of state transfer is ：buy2 = max(buy2, sell1 - prices[i]);
• For the fifth case , The calculation of profit needs to sell another share on the basis of the fourth case . So we need to calculate the fourth case first , Then traverse to prices[i] When , Decide whether to sell . If the profit from selling the first stock and then buying the second stock is the largest , The biggest profit from selling the current stock , Then sell the current stock . The equation of state transfer is ：sell2 = max(sell2, prices[i] + buy2);

The final sell2 That's the answer we need .

/** * @param {number[]} prices * @return {number} */
var maxProfit = function (prices) {
    
  const n = prices.length;
  let buy1 = -prices[0];
  let sell1 = 0;
  let buy2 = -prices[0];
  let sell2 = 0;

  for (let i = 1; i < n; i++) {
    
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, prices[i] + buy1);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, prices[i] + buy2);
  }

  return sell2;
};