123. the best time to buy and sell shares III

Original link ：123. The best time to buy and sell stocks III

 

solution:

        Dynamic programming ：

State means ：dp[i][j][k] Express dp[ Days ][ Whether or not you own shares ][ Number of transactions completed ] Maximum profit earned .

State shift ： Already commented in the code

const int INF = 0x3f3f3f3f;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // Define 3D array 
        //dp[i][j][k] Express dp[ Days ][ Whether or not you own shares ][ Number of transactions ] Maximum profit obtained 
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (2, vector<int> (3, 0)));

        dp[1][1][0] = -prices[0];
        dp[1][0][0] = 0;

        // It is impossible to complete the transaction on the first day 
        dp[1][0][1] = -INF;
        dp[1][0][2] = -INF;
        //  It can't have been sold on the first day 
        dp[1][1][1] = -INF;
        dp[1][1][2] = -INF;

        for(int i = 2;i <= n;i++) {
            dp[i][0][0] = 0;    // No shares , No transaction , Profit is 0.

            // The maximum value of one transaction has been transferred from the stocks held but not traded on the previous day and the stocks not held on the previous day 
            dp[i][0][1] = max(dp[i - 1][1][0] + prices[i - 1], dp[i - 1][0][1]);

            // The trading of stocks held on the previous day and the trading of stocks not held on the previous day have been completed 2 Transfer of maximum value of transactions 
            dp[i][0][2] = max(dp[i - 1][1][1] + prices[i - 1], dp[i - 1][0][2]);

            // Transfer from the maximum value of stocks not held in the previous day to the maximum value of stocks purchased today and held in the previous day 
            dp[i][1][0] = max(dp[i - 1][0][0] - prices[i - 1], dp[i - 1][1][0]);

            // Complete a transaction by not holding shares in the previous day, purchase today and complete an education maximum transfer by holding shares in the previous day 
            dp[i][1][1] = max(dp[i - 1][0][1] - prices[i - 1], dp[i - 1][1][1]);

            dp[i][1][2] = -INF;
        }
        return max(max(dp[n][0][2], dp[n][0][1]), 0);
    }
};