Dynamic programming to solve stock problems (Part 1)

Dynamic programming solves the stock problem （ On ）

1. The best time to buy and sell stocks

Title Description

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .
You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .
Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

Example 1：

 Input ：[7,1,5,3,6,4]
 Output ：5
 explain ： In the  2  God （ Stock price  = 1） Buy when , In the  5  God （ Stock price  = 6） Sell when , Maximum profit  = 6-1 = 5 .
      Note that profit cannot be  7-1 = 6,  Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .

Example 2：

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

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

Answer key

Ideas ： The overall goal is to find two numbers , To maximize the difference , And the small one is on the left

1. We can build a bp Array , The profit of each sale is stored in the noodles , Write it down as profit = The number behind - The previous numbers finally compare the maximum value of all profits
2. Every time you make a profit , We first find the smallest number , Write it down as start Then traverse backwards , Find the difference between the following number and this number , namely profit Every time profit, Compare with the last time profit Who is big , Take the largest value if you encounter a smaller number , We will again start to update

/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    
  const length = prices.length;
  let start = prices[0], profit = 0;
  for(let i = 0; i < length; i++) {
    
    start = Math.min(start, prices[i]);
    profit = Math.max(profit, prices[i] - start);
  }
  return profit;
};

2. The best time to buy and sell stocks II

Title Description

Give you an array of integers prices , among prices[i] Represents a stock i Sky price .
Every day , You can decide whether to buy and / Or sell shares . You at any time most Can only hold A wave of Stocks . You can also buy... First , And then in On the same day sell .
return What you can get Maximum profits .

Example 1：

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

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 .
      The total profit is  4 .

Example 3：

 Input ：prices = [7,6,4,3,1]
 Output ：0
 explain ： under these circumstances ,  There is no positive profit from trading , So you can get the maximum profit by not participating in the transaction , The biggest profit is  0 .

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

Answer key

Define the State dp[i][0] It means the first one i The maximum profit of holding shares after trading for days ,dp[i][1] It means the first one i After days of trading, there is no maximum profit of any stock in hand （i from 0 Start ）.

consider dp[i][0] Transfer equation of , The possible transfer status is that one stock has been held the previous day , namely dp[i−1][0], Or there were no stocks at the end of the previous day , namely dp[i−1][1], At this time, we want to buy it , And reduce prices[i] Revenue . The following transfer equations can be listed ：dp[i][0]=max{dp[i−1][0], dp[i−1][1]−prices[i]}

Consider again dp[i][1], Consider the transition state in the same way , If there is no stock in hand after trading on this day , Then the possible transition state is that there are no stocks the day before , namely dp[i−1][1], Or hold a stock at the end of the previous day , namely dp[i−1][0], At this time we have to sell it , And get prices[i] Revenue . So in order to maximize revenue , We list the following transfer equations ：dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}

For the initial state , According to the definition of state, we can know that 0 At the end of the day dp[0][0]=−prices[0],dp[0][1]=0.

therefore , We just need to calculate the state from front to back . Because after the end of all transactions , The income from holding shares must be lower than that from not holding shares , So this time dp[length−1][1] The benefits must be greater than dp[length−1][0] Of , The final answer is dp[length−1][1].

/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    
  const length = prices.length;
  const dp = Array(length).fill(0).map(() => Array(2).fill(0));
  dp[0][0] = - prices[0];
  
  for(let i = 1; i < length; 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]);
  }  

  return dp[length - 1][1];
};

Of course , Can be set by dp0 and dp1 Two variables instead dp[i][0] and dp[i][1], Reduce space complexity .

/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    
  const length = prices.length;
  let dp0 = -prices[0];
  let dp1 = 0;
  
  for(let i = 1; i < length; i++) {
    
    dp0 = Math.max(dp0, dp1 - prices[i]);
    dp1 = Math.max(dp1, dp0 + prices[i]);
  }  

  return dp1;
};

3. The best time to buy and sell stocks includes handling fees

Title Description

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

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

Answer key

Define the State dp[i][0] It means the first one i The maximum profit of holding shares after trading for days ,dp[i][1] It means the first one i I don't have the maximum profit of the stock in my hand after trading （i from 0 Start ）.

consider dp[i][0] Transfer equation of , Then the possible transfer status is that you have held a stock the previous day , namely dp[i−1][0], Or there were no stocks at the end of the previous day , namely dp[i−1][0], At this time, we want to buy it , And reduce prices[i] Revenue . The following transfer equations can be listed ：dp[i][0]=max{dp[i−1][0], dp[i−1][1]−prices[i]}

Then consider in the same way dp[i][1] Transfer by status , If there is no stock in hand after trading on this day , Then the possible transition state is that there are no stocks the day before , namely dp[i−1][1], Or hold a stock at the end of the previous day , namely dp[i−1][0], At this time we have to sell it , And get prices[i] Revenue , But you have to pay fee The handling charge . So in order to maximize revenue , We list the following transfer equations ：dp[i][1]=max{dp[i−1][1],dp[i−1][0]+prices[i]−fee}

For the initial state , According to the definition of state, we can know that 0 At the end of the day, there was dp[0][1]=0 as well as dp[0][0]=−prices[0].

therefore , We just need to calculate the state from front to back . Because after the end of all transactions , The income from holding shares must be lower than that from not holding shares , So this time dp[length−1][1] The benefits must be greater than dp[length−1][1] Of , The final answer is dp[length−1][1].

Of course , Can be set by dp0 and dp1 Two variables instead dp[i][0] and dp[i][1], Reduce space complexity .

/** * @param {number[]} prices * @param {number} fee * @return {number} */
var maxProfit = function(prices, fee) {
    
    const length = prices.length;
    let [dp0, dp1] = [-prices[0], 0];
    
    for(let i = 0; i < length; i++) {
    
      dp0 = Math.max(dp0, dp1 - prices[i]);
      dp1 = Math.max(dp1, dp0 + prices[i] - fee);
    }

    return dp1;
};