代码随想录算法训练营第四十七天|LeetCode123 买卖股票的最佳时机Ⅲ

题1：

指路：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

思路与代码：

买卖股票专题中三者不同的是Ⅰ为只买卖一次，Ⅱ可多次买卖，Ⅲ最多可买卖两次。那么我们将买买卖行为分为五个状态部分(可延续前几天已有的状态，之前说过分两种情况，可延续前面已经买入/卖出，也可以是今天才买入/卖出)。定义一个数组dp[i][j]，其中i为第i天，j为第j个状态，那么dp[i][j]的含义为第i天在状态j的情况下手头的最大现金。那么从j开始讨论：当j=0时，表示这一天对股票无操作，当j=1时表示第一次持有，当j=2时表示第一次卖出，当j=3时表示第二次买入，当j=4时表示第二次卖出。因为卖出状态时永远比买入状态时手头现金多，所以我们在第一次卖出和第二次卖出中求得较大值。在递推公式部分，第i天无操作的股票状态延续前一天，即dp[i][0]=dp[i-1][0]，第一天买入的股票状态就是在前面说的延续状态和新开状态中取较大值，即dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])，类似得出第一次卖出，第二次买入和第二次卖出的情况。注意的是，买入的时候要减去股票的买入金额(因为求的是手头的金额)，卖出的时候要加上股票的卖出金额(卖出后手头就有钱了)。代码如下：

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];  // 第一次买入dp[0][3] = -prices[0];  // 第二次买入 for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[i - 1][0];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]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);  // 二次卖出}return max(dp[prices.size() - 1][2], dp[prices.size() - 1][4]);}
};