代码随想录算法训练营第三十五天任务
- 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)
动态规划：
确定dp数组的下标及其含义
dp[i][0]：表示第i天持有股票拥有的最多金额。（持有不代表当天买入，还有可能前几天买入，没买出，一直持有）
dp[i][1]：表示第i天不持有股票拥有的最多金额。确定递推公式
第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])初始化
由递推公式可知：第i天由第i-1天推导而来
dp[0][1]: 表示第0天不持有股票, 所以dp[0][1] = 0
dp[0][0]: 表示第0天持有股票，所以dp[0][0] = -prices[0]确定遍历顺序
从前往后举例推导
输入：[7,1,5,3,6,4]
| i | dp[i][0] | dp[i][1] |
|---|---|---|
| 0 | -7 | 0 |
| 1 | -1 | 0 |
| 2 | -1 | 4 |
| 3 | -1 | 4 |
| 4 | -1 | 5 |
| 5 | -1 | 5 |
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步曲安排！
确定dp数组的下标及其含义
每天有5种状态：状态 含义 0 不操作 1 第一次持有 2 第一次不持有 3 第二次持有 4 第二次不持有 dp[i][j]表示第 i 天的第 j 种状态下的最大金额。
确定递推公式
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])初始化
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. 这列数后续也没用到。确定遍历顺序
从前往后举例推导
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)
