The optimal time to buy and sell stocks includes the freezing period (leetcode-309)

The best time to buy and sell stocks includes a freeze period （LeetCode-309）

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

Tips ：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

Ideas

Five steps

1. dp[i][j] The meaning of
   • Four kinds of state
     • State one ： Buy stock status （ Buying stocks today or before has no operation ）
     • State two ： Sold the stock two days ago , Passed the freezing period
     • State three ： Sell shares today
     • State four ： Today is the freezing period
2. The recursive formula
   • $dp[i][0]$ Can be derived from two states
     • The first $i-1$ Days holding shares , It is equal to $dp[i-1][0]$
     • The first $i$ Days to buy shares （ Buy today ）, There are two situations
       • The day before was frozen ：$dp[i-1][3]-prices[i]$
       • The previous day was to keep selling stocks ：$dp[i-1][1]-prices[i]$
     • Choose the one with the most cash , That is, the greater of the two
   • $dp[i][1]$ Can be derived from two states
     • The first $i-1$ Day is already state two , It is equal to $dp[i-1][1]$
     • The day before was frozen , It is equal to $dp[i-1][3]$
     • Choose the one with the most cash , That is, the greater of the two
   • $dp[i][2]$ From only one state
     • It must have been a state of buying stocks the day before （ State one ）：$dp[i-1][0]+prices[i]$
   • $dp[i][3]$ From only one state
     • It must have been the state of selling stocks the day before （ State three ）：$dp[i-1][2]$
3. Array initialization
   • dp[0][0] It means the first one 0 Days to buy shares , So it's equal to $-price[0]$
4. traversal order
   • Before and after

Code display

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

This question is very convoluted , I can't write without looking at the solution .