代码随想录算法训练营第三十五天 | 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机
贪心思路：前期尽可能地低价买入，后期尽可能地高价卖出。

classSolution{public:intmaxProfit(vector<int>&prices){intlow=INT_MAX;intprofit=0;for(inti=0;i<prices.size();++i){low=min(low,prices[i]);// 寻找低点profit=max(profit,prices[i]-low);}returnprofit;}};

时间复杂度：O(n)
空间复杂度：O(1)

动态规划：

1. 确定dp数组的下标及其含义
   dp[i][0]：表示第i天持有股票拥有的最多金额。（持有不代表当天买入，还有可能前几天买入，没买出，一直持有）
   dp[i][1]：表示第i天不持有股票拥有的最多金额。

2. 确定递推公式
   第i天持有股票，由 “第i天之前持有股票” 和 “第i天买入股票”两种状态推导而来: dp[i][0] = max(dp[i-1][0], - prices[i])
   另外注意：题目要求是一次交易，所以第i天买入股票不能由dp[i-1][1]-prices[i] 而来。
   第i天不持有股票，由 “第i天之前不持有股票” 和 “第i天卖出股票”两种状态推导而来: dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

3. 初始化
   由递推公式可知：第i天由第i-1天推导而来
   dp[0][1]: 表示第0天不持有股票, 所以dp[0][1] = 0
   dp[0][0]: 表示第0天持有股票，所以dp[0][0] = -prices[0]

4. 确定遍历顺序
   从前往后

5. 举例推导
   输入：[7,1,5,3,6,4]

classSolution{public:intmaxProfit(vector<int>&prices){vector<vector<int>>dp(prices.size(),vector<int>(2,0));dp[0][0]-=prices[0];// 表示第0天持有股票dp[0][1]=0;// 表示第0天不持有股票for(inti=1;i<prices.size();++i){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}returndp[prices.size()-1][1];}};

时间复杂度：O(n)
空间复杂度：O(n)
还可以用翻滚数组，使空间复杂度为O(1)

122.买卖股票的最佳时机II

题目链接：122.买卖股票的最佳时机II
这道题和上一道题的区别就在于可以多次交易。
由上述动规五步曲可知，只一点不同，就是 第i天持有股票，由 “第i天之前持有股票” 和 “第i天买入股票”两种状态推导而来: dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) 第i天买入股票可由前一天不持有股票金额推导而来。

classSolution{public:intmaxProfit(vector<int>&prices){vector<vector<int>>dp(prices.size(),vector<int>(2,0));dp[0][0]-=prices[0];// 表示第0天持有股票dp[0][1]=0;// 表示第0天不持有股票for(inti=1;i<prices.size();++i){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);// 与 121. 买卖股票的最佳时机不同之处dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}returndp[prices.size()-1][1];}};

时间复杂度：O(n)
空间复杂度：O(n)
还可以用翻滚数组，使空间复杂度为O(1)

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

题目链接：123.买卖股票的最佳时机III
这道题要求 最多可以完成 两笔 交易。这个限制就像背包一样，不超过。
想不出来，看题解了，原来是分状态。
动规5步曲安排！

1. 确定dp数组的下标及其含义
   每天有5种状态：

   状态	含义
   0	不操作
   1	第一次持有
   2	第一次不持有
   3	第二次持有
   4	第二次不持有

   dp[i][j]表示第 i 天的第 j 种状态下的最大金额。

2. 确定递推公式
   dp[i][1] : 第 i 天第一次持有股票，由 “第 i 天之前第一次持有股票” 和 “第 i 天买入股票”两种状态推导而来。
   dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
   dp[i][2]: 第 i 天第一次不持有股票，由 “第 i 天之前第一次不持有股票” 和 “第 i 天卖出股票”两种状态推导而来。
   dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
   dp[i][3]: 第 i 天第二次持有股票，由 “第 i 天之前第二次持有股票” 和 “第 i 天买入股票”两种状态推导而来。
   dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
   dp[i][4]: 第 i 天第二次不持有股票，由 “第 i 天之前第二次不持有股票” 和 “第 i 天卖出股票”两种状态推导而来。
   dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])

3. 初始化
   dp[0][0]: 表示第0天不操作，dp[0][0] = 0.
   dp[0][1]: 表示第0天第一次持有, dp[0][1] = -prices[0]
   dp[0][2]: 表示第0天第一次不持有, dp[0][2] = 0
   dp[0][3]: 表示第0天第二次持有, dp[0][3] = -prices[0]
   dp[0][4]: 表示第0天第二次不持有, dp[0][4] = 0
   dp[i][0] : 表示第 i 天什么都不操作，不是第一次持有/不持有，第二次持有/不持有的任何一个状态，无操作，dp[i][0] = 0. 这列数后续也没用到。

4. 确定遍历顺序
   从前往后

5. 举例推导
   prices = [3,3,5,0,0,3,1,4]

   i	prices[i]	dp[i][0]	dp[i][1]	dp[i][2]	dp[i][3]	dp[i][4]
   0	3	0	-3	0	-3	0
   1	3	0	-3	2	-3	2
   2	5	0	-3	2	-3	2
   3	0	0	0	2	2	2
   4	0	0	0	2	2	2
   5	3	0	0	3	2	5
   6	1	0	0	3	2	5
   7	4	0	0	4	2	6

classSolution{public:intmaxProfit(vector<int>&prices){vector<vector<int>>dp(prices.size(),vector<int>(5,0));// dp[0][0] = 0; // 表示第0天不操作dp[0][1]=-prices[0];// 表示第0天第一次持有// dp[0][2] = 0; // 表示第0天第一次不持有dp[0][3]=-prices[0];// 表示第0天第二次持有// dp[0][4] = 0; // 表示第0天第二次不持有for(inti=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][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]);}returndp[prices.size()-1][4];}};

时间复杂度：O(n)
空间复杂度：O(n)
还可以用翻滚数组，使空间复杂度为O(1)