123.买卖股票的最佳时机III
要求：最多买卖两次股票，获得最大利润
思路：
分成四个状态
第一次买 卖， 第二次买 卖
代码 ：
1 // 最多只能进行一笔交易 2 // 难点： 3 // 1，只能买卖两次 4 // 2，中间可能有空隙：一直不持有 5 // 6 // 持有：dp[i][0] 不持有：dp[i][1] 7 // 8 // 持有： 9 // 一直持有 dp[i-1][0] 10 // 刚持有（如何保证只能买卖两次）dp[i-1][1]-prices[i] -》能否设置单次买卖的场景，然后选择其中最大的两次？ 11 // 12 // 不持有 13 // dp[i-1][1] 14 // dp[i-1][0]+prices[i] 15 // 16 // 如果强制选择前两次，可能一次里面包含着另一次 17 // 18 // 分成四种情况: 第一次买 卖 第二次买 卖 19 // dp[i][0] [1] [2] [3] 20 // 21 int maxProfit(vector<int>& prices) { 22 if (prices.size() == 1) return 0; 23 vector<vector<int>> dp(prices.size(), vector<int>(4, 0)); 24 25 dp[0][0] = -prices[0]; 26 dp[0][1] = 0; 27 dp[0][2] = -prices[0]; 28 dp[0][3] = 0; 29 30 for (int i = 1; i < prices.size(); i++) 31 { 32 dp[i][0] = max(dp[i - 1][0], -prices[i]); 33 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]); 34 dp[i][2] = max(dp[i - 1][2], -prices[i] + dp[i - 1][1]); 35 dp[i][3] = max(dp[i - 1][3], prices[i] + dp[i - 1][2]); 36 } 37 38 return dp[prices.size() - 1][3]; 39 }