目录
题目描述
这道题在第121题121. Best Time to Buy and Sell Stock和第122题leetcode 122. Best Time to Buy and Sell Stock II基础上进一步限制条件。
仍然按照动态规划的思路解决。
第一步，明确并理解dp数组及下标的含义
//约定好，下面提到的第一只股票指的是在这n天内第一次买入的股票，第二只股票指的是第二次买入的股票
//dp[i][0]表示从第0天到第i天结束，此时仍然处于没有买过股票的状态下的最大利润
//dp[i][1]表示从第0天到第i天结束，此时处于持有第一只股票的状态下的最大利润
//dp[i][2]表示从第0天到第i天结束，此时处于已经卖出第一只股票但还没买入第二只股票的状态下的最大利润
//dp[i][3]表示从第0天到第i天结束，此时处于持有第二只股票的状态下的最大利润
//dp[i][4]表示从第0天到第i天结束，此时处于已经卖出第二只股票的状态下的最大利润
int n = prices.size();
//约定好，下面提到的第一只股票指的是在这n天内第一次买入的股票，第二只股票指的是第二次买入的股票
//dp[i][0]表示从第0天到第i天结束，此时仍然处于没有买过股票的状态下的最大利润
//dp[i][1]表示从第0天到第i天结束，此时处于持有第一只股票的状态下的最大利润
//dp[i][2]表示从第0天到第i天结束，此时处于已经卖出第一只股票但还没买入第二只股票的状态下的最大利润
//dp[i][3]表示从第0天到第i天结束，此时处于持有第二只股票的状态下的最大利润
//dp[i][4]表示从第0天到第i天结束，此时处于已经卖出第二只股票的状态下的最大利润
vector<vector<int>> dp(n);
for(int i = 0;i < n;i++)
dp[i].resize(5);第二步，分析明确并理解递推公式
1.求dp[i][0]
//很容易理解，按照定义i>=0,dp[i][0]都是0
dp[i][0] = 0;
2.求dp[i][1]
//第i天结束时处于持有第一只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第一只股票的状态（对应状态dp[i-1][1]），第i天什么都不做
//二是第i天第一次买入股票（需支付prices[i]），第i天能第一次买入股票的前提是前一天（第i-1天）处于没有买过股票的状态（对应状态dp[i-1][0]）
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);
3.求dp[i][2]
//第i天结束时处于已经卖出第一只股票但还没买入第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）,第i天什么都不做
//二是第i天卖出了第一只股票（收入prices[i]）,第i天能卖出第一只股票的前提是第i-1天处于持有第一只股票的状态(对应dp[i-1][1])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
4.求dp[i][3]
//第i天结束时处于持有第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第二只股票的状态（对应dp[i-1][3]）,第i天什么都不做
//二是第i天买入了第二只股票（需支付prices[i]）,第i天能买入第二只股票的前提是第i-1天处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]);
5.求dp[i][4]
//第i天结束时处于已经卖出第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第二只股票的状态（对应dp[i-1][4]）,第i天什么都不做
//二是第i天卖出了第二只股票(收入prices[i])，第i天能卖出第二只股票的前提是第i-1天处于持有第二只股票的状态（对应dp[i-1][3]）
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
//很容易理解，按照定义i>=0,dp[i][0]都是0
dp[i][0] = 0;
//第i天结束时处于持有第一只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第一只股票的状态（对应状态dp[i-1][1]），第i天什么都不做
//二是第i天第一次买入股票（需支付prices[i]），第i天能第一次买入股票的前提是前一天（第i-1天）处于没有买过股票的状态（对应状态dp[i-1][0]）
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);
//第i天结束时处于已经卖出第一只股票但还没买入第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）,第i天什么都不做
//二是第i天卖出了第一只股票（收入prices[i]）,第i天能卖出第一只股票的前提是第i-1天处于持有第一只股票的状态(对应dp[i-1][1])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
//第i天结束时处于持有第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第二只股票的状态（对应dp[i-1][3]）,第i天什么都不做
//二是第i天买入了第二只股票（需支付prices[i]）,第i天能买入第二只股票的前提是第i-1天处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]);
//第i天结束时处于已经卖出第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第二只股票的状态（对应dp[i-1][4]）,第i天什么都不做
//二是第i天卖出了第二只股票(收入prices[i])，第i天能卖出第二只股票的前提是第i-1天处于持有第二只股票的状态（对应dp[i-1][3]）
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);第三步，理解dp数组如何初始化
dp[0][0] = 0;//很容易理解，按照定义i>=0,dp[i][0]都是0
dp[0][1] = -prices[0];//第0天买入了股票，没有卖出，支付prices[0],利润变为负prices[0]
dp[0][2] = 0;//第0天买入了然后又卖出了股票，利润是0
dp[0][3] = -prices[0];//第0天买入了卖出了，然后又第二次买入了股票，没有卖出，利润是负prices[0]
dp[0][4] = 0;//第0天买入了卖出了，然后又买入了又卖出了股票。折腾两次，利润是0
第四步，理解遍历顺序
由递推公式可知第i个状态依赖于第i-1个状态，因此i要从小到大遍历。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
//约定好，下面提到的第一只股票指的是在这n天内第一次买入的股票，第二只股票指的是第二次买入的股票
//dp[i][0]表示从第0天到第i天结束，此时仍然处于没有买过股票的状态下的最大利润
//dp[i][1]表示从第0天到第i天结束，此时处于持有第一只股票的状态下的最大利润
//dp[i][2]表示从第0天到第i天结束，此时处于已经卖出第一只股票但还没买入第二只股票的状态下的最大利润
//dp[i][3]表示从第0天到第i天结束，此时处于持有第二只股票的状态下的最大利润
//dp[i][4]表示从第0天到第i天结束，此时处于已经卖出第二只股票的状态下的最大利润
vector<vector<int>> dp(n);
for(int i = 0;i < n;i++)
dp[i].resize(5);
dp[0][0] = 0;//很容易理解，按照定义i>=0,dp[i][0]都是0
dp[0][1] = -prices[0];//第0天买入了股票，没有卖出，支付prices[0],利润变为负prices[0]
dp[0][2] = 0;//第0天买入了然后又卖出了股票，利润是0
dp[0][3] = -prices[0];//第0天买入了卖出了，然后又第二次买入了股票，没有卖出，利润是负prices[0]
dp[0][4] = 0;//第0天买入了卖出了，然后又买入了又卖出了股票。折腾两次，利润是0
for(int i = 1;i < n;i++){
//很容易理解，按照定义i>=0,dp[i][0]都是0
dp[i][0] = 0;
//第i天结束时处于持有第一只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第一只股票的状态（对应状态dp[i-1][1]），第i天什么都不做
//二是第i天第一次买入股票（需支付prices[i]），第i天能第一次买入股票的前提是前一天（第i-1天）处于没有买过股票的状态（对应状态dp[i-1][0]）
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);
//第i天结束时处于已经卖出第一只股票但还没买入第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）,第i天什么都不做
//二是第i天卖出了第一只股票（收入prices[i]）,第i天能卖出第一只股票的前提是第i-1天处于持有第一只股票的状态(对应dp[i-1][1])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
//第i天结束时处于持有第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于持有第二只股票的状态（对应dp[i-1][3]）,第i天什么都不做
//二是第i天买入了第二只股票（需支付prices[i]）,第i天能买入第二只股票的前提是第i-1天处于已经卖出第一只股票但还没买入第二只股票的状态（对应dp[i-1][2]）
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]);
//第i天结束时处于已经卖出第二只股票的状态有两种可能的原因：
//一是第i-1天就已经处于已经卖出第二只股票的状态（对应dp[i-1][4]）,第i天什么都不做
//二是第i天卖出了第二只股票(收入prices[i])，第i天能卖出第二只股票的前提是第i-1天处于持有第二只股票的状态（对应dp[i-1][3]）
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
}
return max(max(dp[n-1][0],dp[n-1][2]),dp[n-1][4]);
}
};经过上面的分析，很容易发现，dp[i][0]，即从第0天到第i天结束此时仍然处于没有买过股票的状态下的最大利润，是可以不定义的，可以节省空间开销。