代码随想录打卡Day41

最近事情好多。。全堆一块了，今天先写两题吧，剩下一题明天解决。

121. 买卖股票的最佳时机

这道题纯不会，不知道该怎么构造dp数组，更不知道dp数组的含义，看完讲解以后感觉这样的dp数组构造还挺巧妙的，第一次见这样构造dp数组的。这道题的循环中需要同时维护两个状态，一种是第i天保持持有股票状态时的最大收益（不一定是在第i天买入，有可能在之前就买入了），一种是第i天保持未持有股票状态时的最大收益（不一定是在第i天卖出，也有可能是在之前就已经卖出了），这样定义两个状态就把所有状态都包含了，由于这道题只能买卖一次股票，所以状态转移很简单：
1.当第i天持有股票时
如果在第i天之前就已经买入股票了，那么第i天仍然持有股票，则获得的收益已经被定死，就与前一天持有股票的收益是相同的，因为持有股票而不卖出的话，收益一直都是负数（购买股票需要花钱，收益就是买入当天股票价格的负数）；如果是第i天当天买入的股票，则当天的收益为-prices[i]（买股票的成本）。将两种情况作比较取较大值，只要当天的价格相比于之前的价格高，那么当天买入的收益一定不是最大的，收益最大化的必要条件之一是购入股票的成本尽可能低。
2.当第i天未持有股票时
如果第i天之前就已经卖出股票，那么后序也就不能再买卖股票，属于是买定离手，不能反悔了，后面的收益也就不再变动，和前一天未持有股票的收益相同；如果是第i天才把股票卖出，则前一天必然是持有股票的状态，直接将前一天持有股票的最大收益（此前购买股票的最低成本）与当天股票价格相加即可，收益最大化的另一必要条件之一是卖出股票的价格尽可能高。
了解了dp数组的具体含义，初始化也很好办了。

class Solution {
public:int maxProfit(vector<int>& prices) {//1.确定dp[i][0]的含义：第i天保持持有股票情况下，所能获得的最大收益为dp[i][0]//      dp[i][1]的含义：第i天未持有股票的情况下，所能获得的最大收益为dp[i][1]//2.确定递推公式dp[i][0] = max(dp[i - 1][0], -prices[i]);//             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])//3.dp数组初始化 dp[0][0] = -prices[0], dp[0][1] = 0;//4.确定遍历顺序：从小到大遍历//5.打印数组(省略)int m = prices.size();vector<vector<int>> dp(m, vector<int> (2));//初始化dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < m; 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]);}return dp[m - 1][1];}
};

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

这道题比上一道题略难一点，但是思路大同小异，这道题与上一道题的区别在于这道题可以买卖多次股票。在代码实现中区别体现在哪里呢？主要是体现在递推公式上。
1.当第i天持有股票时
若是在第i天之前买入了股票，则在上一次买入股票之前可能还涉及多次股票买卖操作，因此在最近一次买入股票后，收益未必是负数（此前可能通过多次买卖股票实现了盈利），至少在第i - 1天依然是持有股票的状态，所以这种情况下的最大收益为dp[i - 1][0];若在第i天买入了股票，则第i - 1天必然是未持有股票的状态，因此这种情况下的最大收益是dp[i - 1][1] - prices[i]；两者取较大值即可。
2.当第i天未持有股票时
若在第i天之前就已经是未持有状态（可能从未买过，也可能已经卖出），则至少在i - 1天也处于未持有状态，则这种情况下第i天的最大收益应当与第i - 1天的最大收益持平；若在第i天才卖出股票，则第i - 1天必然是持有股票的状态，则用第i - 1持有股票的最大收益加上第i天的股票价格即可。
除了递推公式上有细微差别外，其余地方完全相同。

class Solution {
public:int maxProfit(vector<int>& prices) {//1.确定dp[i][0]的含义：第i天保持持有股票情况下，所能获得的最大收益为dp[i][0]//      dp[i][1]的含义：第i天未持有股票的情况下，所能获得的最大收益为dp[i][1]//2.确定递推公式dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])//3.dp数组初始化 dp[0][0] = -price[0], dp[0][1] = 0;//4.确定遍历顺序：从小到大遍历//5.打印数组(省略)int m = prices.size();vector<vector<int>> dp(m, vector<int> (2));//初始化dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < m; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[m - 1][1];}
};

实在是太累了，明天再说。

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

这道题是困难题，第一道题是必须买卖一次，第二道题是没有买卖次数限制，这道题是最多可以买卖两次，也可以不做任何买卖。这道题的难点主要还是在于dp数组的构造。主要有以下5种状态：
1.第i天为从未进行过任何买卖操作的状态
在第i天及以前，从未进行过任何股票的买卖操作，此时取得的最大收益必然为0。
2.第i天为第一次持有股票的状态
若在第i天之前已经买入了股票，至少在i - 1天也是持有状态，则第i天的最大收益为dp[i - 1][1]（股票尚未卖出）;若在第i天买入股票，则第i天的最大收益为dp[i - 1][0] - prices[i]。二者需要取最大值。
3.第i天为第一次未持有股票的状态
若在第i天之前已经卖出了股票，至少在第i - 1天也是未持有状态，则第i天的最大收益为dp[i - 1][2] (第二次股票尚未买入)；若在第i天卖出股票，则第i天的最大收益为dp[i - 1][1] + prices[i]。二者需要取最大值。
4.第i天为第二次持有股票的状态
若在第i天之前已经买入了第二次股票，至少在第i - 1天也是持有状态，则第i天的最大收益为dp[i - 1][3]（股票尚未卖出）；若在第i天当天买入了第二次股票，则第i天的最大收益为dp[i - 1][2] - prices[i]。二者需要取最大值。
5.第i天为第二次未持有股票的状态
若在第i天之前已经卖出了第二次股票，至少在第i - 1天也是未持有状态，则第i天的收益为dp[i - 1][4]（股票已经卖出）；若在第i天当天卖出股票，则第i天的最大收益为dp[i - 1][3] + prices[i]。
注意，股票允许当天买入当天卖出，所以直接返回最后一天未持有股票的最大收益即可（如果只需要买卖一次就能得到最大收益，在此基础上选择某一天当天买卖第二次股票即可）。
初始化和遍历顺序没什么难的，这里就不写了。

class Solution {
public:int maxProfit(vector<int>& prices) {//1.确定dp[i][0]的含义：第i天仍然没有进行过任何买卖操作的情况下，所能获得的最大收益为dp[i][0]//      dp[i][1]的含义：第i天为第一次持有股票的情况下，所能获得的最大收益为dp[i][1]//      dp[i][2]的含义：第i天为第一次未持有股票的情况下，所能获得的最大收益为dp[i][2]//      dp[i][3]的含义：第i天为第二次持有股票的情况下，所能获得的最大收益为dp[i][3]//      dp[i][4]的含义：第i天为第二次未持有股票的情况下，所能获得的最大收益为dp[i][4]//2.确定递推公式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])//3.dp数组初始化 dp[0][0] = 0;//              dp[0][1] = -prices[0];//              dp[0][2] = 0;//              dp[0][3] = -prices[0];//              dp[0][4] = 0;//4.确定遍历顺序：从小到大遍历//5.打印数组(省略)int m = prices.size();vector<vector<int>> dp(m, 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 < m; 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[m - 1][4];}
};