[dynamic planning -- the best period series for buying and selling stocks]

problem 1： Force buckle question link
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

Dynamic programming 5 Step curve

1. determine dp Array (dp table) And the meaning of subscript .
  dp[i][0] It means the first one i The most cash you can get from holding stocks in a day .
   Be careful “ hold ” Doesn't mean it's the same day “ purchase ”, Maybe I bought it yesterday , Not sold today , keep “ hold ” state .
   At the beginning, the cash was 0, Add the number i The cash for buying stocks is -prices[i], It's a negative number .
  dp[i][1] It means the first one i Days don't get the most cash from holding stocks .
2. Determine the recurrence formula 
   If the first i Days of holding shares dp[i][0],  Then it can be deduced from two states 
 -  The first i-1 Hold stocks within days , Then keep the status quo , The cash obtained is the cash obtained from holding shares yesterday   namely ：dp[i - 1][0]
 -  The first i Days to buy shares , The cash obtained is the cash obtained after buying today's stocks, that is ：-prices[i]
    that dp[i][0] You should choose the one with the largest cash , therefore dp[i][0] = max(dp[i - 1][0], -prices[i]);
    If the first i If you don't hold shares for days, that is dp[i][1],  It can also be deduced from two states 
 -  The first i-1 Don't hold stocks for days , Then keep the status quo , The cash obtained is the cash obtained from not holding shares yesterday   namely ：dp[i - 1][1]
 -  The first i Days to sell shares , The cash obtained is the cash obtained after selling at today's good stock price, that is ：prices[i] + dp[i -
   1][0] Again dp[i][1] Take one of the biggest ,dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i -
   1][0]);
3. initialization dp Array 
 -  By recurrence formula  dp[i][0] = max(dp[i - 1][0], -prices[i]);  and  dp[i][1] = max(dp[i
 - 1][1], prices[i] + dp[i - 1][0]); It can be seen that 
 -  The basis is to start from dp[0][0] and dp[0][1] derived .
 -  that dp[0][0] It means the first one 0 Days holding shares , Holding stocks at this time must be buying stocks , Because it can't be pushed out the day before , therefore dp[0][0] -=
   prices[0];
 - dp[0][1] It means the first one 0 Days do not hold shares , If you don't hold stocks, then cash is 0, therefore dp[0][1] = 0;
4. Determine the traversal order 
   As can be seen from the recurrence formula ,dp[i] It's all by dp[i-1] Derived from , Then the traversal order must be from front to back .
5. Give an example to deduce dp Array 
   With [7,1,5,3,6,4] For example ,dp The state of the array is shown in the figure ：

dp[5][1] It's the end result .

The code is as follows ：

#include<iostream>
#include<vector>
using namespace std;
class Solution{
    
	public:
		int maxProfit(vector<int> &prices) {
    
			int len = prices.size();
			vector<vector<int>> dp(len,vector<int>(2));
			dp[0][0] = -prices[0];//dp[i][0] It means the first one i The most cash you can get from holding shares in a day 
			dp[0][1] = 0;//dp[i][1] It means the first one i The most cash you can get from not holding stocks for days 
			for (int i = 1; i < len; i++) {
    
				dp[i][0] = max(dp[i-1][0],-prices[i]);
				dp[i][1] = max(dp[i-1][1],dp[i][0]+prices[i]);
			}
			return dp[len-1][1];
		}
};
int main() {
    
	Solution Q;
	vector<int> price(6);
	for (int i = 0; i < 6; i++) {
    
		cin>>price[i];
	}
	cout<<Q.maxProfit(price);
}

problem 2 Force link
Topics and 1 identical , The only difference is that stocks can be bought and sold many times （ Note that there is only one stock , So sell the stock before buying again ）
analysis
This topic and topic 1 The only difference is derivation dp[i][0] When , The first i Days of buying stocks .
subject 1 in , Because stocks can only be bought and sold once in the whole process , So if you buy stocks , So the first i The shares held by Tian are dp[i][0] Namely -prices[i].
In this question, a stock can be bought and sold many times , So when the first i When buying stocks , The cash held may include the profits obtained from buying and selling stocks before .
So the first i Days of holding shares dp[i][0], If it's No i Days to buy shares , The cash obtained is the cash obtained from not holding shares yesterday subtract Today's stock price namely ：dp[i - 1][1] - prices[i].
Specifically analyze the five steps of the dynamic rule of reference topic one .
The code is as follows ：

#include<iostream>
#include<vector>
using namespace std;
class Solution{
    
	public:
		int Maxprofit(vector<int> &prices) {
    
			vector<vector<int>> dp(prices.size(),vector<int>(2));
			dp[0][0] = -prices[0];
			dp[0][1] = 0;
			for (int i = 1; i < prices.size(); i++) {
    
				dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]);
				dp[i][1] = max(dp[i-1][1],prices[i] + dp[i-1][0]);
			}
			return dp[prices.size()-1][1];
		}
};