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

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];}
};

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