State machine DP, refer to labuladong’s solution

So let’s start with the state representation, so there are three states, the number of days, the maximum number of trades that are currently taking place, and whether you currently own stocks. Therefore, we can use dp[I][k][0 or 1] to represent: the current is the ith day (I starts from 0), the maximum number of transactions currently allowed is K (here, we consider the number of transactions to be the number of buying stocks), 0 means that the stock is not currently held, and 1 means the maximum profit of the stock currently held.

After listing the state representation, we need to consider the state transition equation. Here is the state transition diagram drawn by Labuladong:

Buy, sell, and REST indicate buy, sell, and do not operate, respectively.

As can be seen from the state transition diagram, for a state that does not hold stocks, it can only be transferred by two states: Sell and REST. That is to say, it is possible to (1) hold stocks the previous day and sell them to become today’s state; And (2) didn’t own stocks the day before, so they still don’t own stocks today. For a stock holding state, there are only two states to transfer from: Buy and REST. That is, it is possible (1) to buy a stock today without owning a stock the day before; And (2) held the stock the day before, not today.

So we know how states are transferred, and we can think about transition equations.

For each day, for dp[I][k][0] (day I, k trades, currently no stock), we already know that it is transferred from two states: DP [i-1][k][0] (also no stock yesterday) and DP [i-1][k][1] (held stock yesterday, sold today), Due to dp [I – 1] [k] [0] to dp said [I] [k] [0] rest (no operation), so the income remains the same: dp [I] [k] [0] = dp [I – 1] [k] [0]; From dp [I – 1] [k] [1] is transferred to dp [I] [k] [0] said in the first day I sell stocks, so is the dp [I] [k] [0] = dp [k] [I – 1] [1] + prices [I]; Dp [I][k][0] = Max (dp[i-1][k][0], dp[i-1][k][1] + prices[I]);

For dp[I][k][1] (day I, k trades, currently holding stocks), we know that it is transferred from two states: DP [i-1][k][1] (also held stocks the previous day) and DP [i-1][K-1][0] (did not own stocks the previous day, but bought stocks today). Because the dp [I – 1] [k] [1] is transferred to dp said [I] [k] [1] rest (no operation), so income remains the same: dp [I] [k] [1] = dp [k] [I – 1] [1]. From dp [I – 1] [0] to [k – 1] dp said [I] [k] [1] in the first day I buy stocks, so is the dp [I] [k] [1] = dp [I – 1] [1] – [k – 1] prices [I]; Dp [I][k][1] = Max (dp[i-1][k][1], dp[i-1][k-1][0] -prices [I]);

So we can iterate over the number of days and transactions per day to determine all the states. The final answer is dp[n-1][K][0] (where n is the size of the prices array, indicating all the days and K is the maximum number of transactions/purchases). This state means that on the last day, the maximum number of transactions is K. Maximum gain from not owning stocks. Why not dp[n-1][K][1]? Since 1 means that you still own the stock, and buying the stock costs money and selling it makes money, it is clear that DP [n-1][K][0] is larger than DP [n-1][K][1].

Now that we have our state representation, we have our state transition equation, we just need to figure out the boundary case, and we can start writing code.

Let’s look at our state transition equation:

dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
Copy the code

Each state is transferred from the previous day, so for day 0 (I == 0), we need to consider it separately. For all trades k, we have dp[0][k][0] = 0, no matter how many trades are made on day 0. We’re still enumerating all k’s), and the returns are 0 (because we don’t own stocks). This state can also be interpreted as buying k times and selling k times on day 0 (we can’t do that, but we’re going to enumerate all the k’s for later calculations), so we’re not making money. If we enumerate all times k, we have dp[0][k][1] = -prices[0], which means prices[0], so no matter how many times prices[0] trade (although prices[I] buy the stock on day 0 at most), the return will always be -prices[0].

Dp [0][k][0], dp[0][k][1], dp[0][k][1], dp[0][k][0], dp[0][K][1]

Notice here that if the maximum number of trades K >= n / 2, since it takes two days to buy and sell, if the number of trades is more than half the number of days, that means there is no limit on the number of trades K, that’s also a separate case, and actually, that’s the second problem in the stock series, And the way you do that is you enumerate whether there’s any arbitrage between each day and the day after that, and if there is, you add prices[I + 1] -prices [I], which means if the price one day is lower than the next day, THEN I buy a stock yesterday and I sell it today. After enumerating all the days, the sum of profits per day is the final answer.

The code is as follows:

class Solution { public: int maxProfit(int K, vector<int>& prices) { int n = prices.size(); If (K >= n / 2) {// if(K >= n / 2) { for(int i = 0; i + 1 < n; ++i) { if(prices[i + 1] > prices[i]) { res += prices[i + 1] - prices[i]; } } return res; } vector<vector<vector<int>>> dp(n, vector<vector<int>>(K + 1, vector<int>(2))); for(int i = 0; i < n; ++i) { for(int k = 1; k <= K; + + k) {if (I = = 0) {/ / edge cases, 0 I I - 1 when crossing the line, separate processing dp [I] [k] [0] = 0; dp[i][k][1] = -prices[i]; continue; } dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]); dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); } } return dp[n - 1][K][0]; // On the last day, K trades are made and the maximum profit can be made if the stock is not owned}};Copy the code