力扣 123. 买卖股票的最佳时机 III

题目来源：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

C++题解：动态规划。至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

一天一共就有四个状态：

第一次持有股票、第一次不持有股票、第二次持有股票、第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 3] 四个状态，dp[i][j]表示第i天状态j所剩最大现金。

需要注意：dp[i][0]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票。

例如 dp[i][0] ，并不是说 第i天一定买入股票，有可能 第 i-1天 就买入了，那么 dp[i][0] 延续买入股票的这个状态。

dp[i][2]，第i天第二次持有股票。dp[0][2]怎么初始化，可以视作之前买进卖出到第0天获益为0，所以dp[0][2]=-prices[0]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n <= 1) return 0;
        // dp[i][j], j为0-3，0第一次买入，1第一次卖出，2第二次买入，3第二次卖出
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] = -prices[0];dp[0][2] = -prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);
        }
        return dp[n-1][3]; // 虽然可能没有第二次卖出，但是第二次卖出的获益一定大于等于第一次获益
    }
};