今天继续学习动规解决相关问题。

123.买卖股票的最佳时机|||

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

思路：

1.本题相比起Day52中的|和||，最大的问题在于限制了买卖两次，因此我们需要将状态设置为五种状态：（1）没有操作，（2）第一次持有股票；（2）第一次不持有股票；（3）第二次持有股票；（4）第二次不持有股票。

2.后两种新增情况的递推公式，我们可以依据原有的（2）和（3）进行变化即可。

3.关于初始化问题，因为本题有说明prices可以是只有一个元素，因此实际上是可以当天买入当天卖出的，因此dp[0][1]和dp[0][3]均初始化为-prices[i]。

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(5));dp[0][0] = 0;dp[0][1] = - prices[0];dp[0][2] = 0;dp[0][3] = - prices[0];dp[0][4] = 0;for(int i = 1; i < prices.size(); i++){dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);}return dp[prices.size() - 1][4];}
};

启发：

1.本题实际上可以把dp[i][0]的状态给优化掉，因为没有操作的情况下现金实际上就是0。

2.本题在最后返回值时可能会选择取最大值返回，但实际上dp[i][4]作为第二次不持有股票的情况，其一定是包含了dp[i][2]的情况的，因此直接返回dp[i][4]即可。

PS：很抱歉今天因为身体不适所以只做了一道题然后解析也基本上偷懒了，日后会重新理解本题（确信）