我把GitHub:https://github.com/youngyangyang04/leetcode-master,的刷机指南都整理好了，方便大家在电脑上阅读。这个仓库每天都会更新。请去给明星一个支持吧！
同时，我还在CodeCloud上同步了一份副本：https://gitee.com/programmercarl/leetcode-master,和那些不方便访问Github的人可以阅读这个。
标题链接：https://leet code-cn . com/problems/best-time-to-buy-and-sell-stock-iii/
给定一个数组，它的第I个元素是给定股票在第I天的价格。
设计一个算法来计算你能获得的最大利润。您最多可以完成两笔交易。
注意：不能同时参与多笔交易(必须先卖出之前的股票再买入)。
示例1:
输入：价格=[3，3，5，0，0，3，1，4]
产出：6
解释：第4天买入(股价=0)，第6天卖出(股价=3)。这种交换可以获利=3-0=3。然后，第7天买入(股价=1)，第8天卖出(股价=4)。这种交换可以获利=4-1=3。
示例2:
输入：价格=[1，2，3，4，5]
输出：4
解释：第1天买入(股价=1)，第5天卖出(股价=5)。这种交换可以获利=5-1=4。注意，不能在第1、2天连续买入股票，然后卖出。因为你同时参与多项交易，所以你必须先卖出之前的股票，然后再买入。
示例3:
输入：价格=[7，6，4，3，1]
输出：0
说明：在这种情况下，没有交易完成，所以最大利润为0。
示例4:
输入：价格=[1]
输出：0
提示：
1=价格。length=10 50=prices[I]=10 5
这个题目是相对于121的。买卖股票的最佳时间和12
2.买卖股票的最佳时机II 难了不少。关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
接来下我用动态规划五部曲详细分析一下：
一天一共就有五个状态， 0. 没有操作
dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
达到dp[i][1]状态，有两个具体操作：
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作：
所以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][4], dp[i - 1][3] + prices[i]);
第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，这个初始值应该是多少呢？
首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
所以dp[0][2] = 0;
第0天第二次买入操作，初始值应该是多少呢？
不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
同理第二次卖出初始化dp[0][4] = 0;
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
以输入[1,2,3,4,5]为例
大家可以看到红色框为最后两次卖出的状态。
现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。
所以最终最大利润是dp[4][4]
以上五部都分析完了，不难写出如下代码：
// 版本一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 dp[prices.size() - 1][4]; }};当然，大家可以看到力扣官方题解里的一种优化空间写法，我这里给出对应的C++版本：
// 版本二class Solution {public: int maxProfit(vector<int>& prices) { if (prices.size() == 0) return 0; vector<int> dp(5, 0); dp[1] = -prices[0]; dp[3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[1] = max(dp[1], dp[0] - prices[i]); dp[2] = max(dp[2], dp[1] + prices[i]); dp[3] = max(dp[3], dp[2] - prices[i]); dp[4] = max(dp[4], dp[3] + prices[i]); } return dp[4]; }};大家会发现dp[2]利用的是当天的dp[1]。但结果也是对的。
我来简单解释一下：
dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1]，即保持买入股票的状态，那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。
如果dp[1]取dp[0] - prices[i]，今天买入股票，那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是尽在再卖出股票，一买一卖收益为0，对所得现金没有影响。相当于今天买入股票又卖出股票，等于没有操作，保持昨天卖出股票的状态了。
这种写法看上去简单，其实思路很绕，不建议大家这么写，这么思考，很容易把自己绕进去！
对于本题，把版本一的写法研究明白，足以！
目前「代码随想录」已经发布了如下手册：
@代码随想录 期待你的关注
