题解 | #买卖股票的最好时机（三）#

好好理解一下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
      if (prices.empty()) {
        return 0;
      }
      //  状态转移：有5种状态，在这5种状态中进行转移。最大值出现在最后一天不持股的状态（有两种）
      //  dp[i][j] 表示截至第i天时最大的收益，j表示截至到当天的状态
      //  j: 没有买过股票；买了一次股票但没有卖出；买了一次股票并且卖出；买了两次股票然后卖出一次；买卖股票两次；
      //  第一天只有买入和没有买0
      //  初始化值小确保状态能够转移
      std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(5, -10000));
      dp[0][0] = 0;
      dp[0][1] = -prices[0];
      
      for (int i = 1; i < prices.size(); ++i) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = std::max(dp[i][0] - prices[i], dp[i - 1][1]);
        dp[i][2] = std::max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
        dp[i][3] = std::max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = std::max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
      }
      
      return std::max(dp[prices.size() - 1][2], dp[prices.size() - 1][4]);
    }
};