刷题打卡day49 121. 买卖股票的最佳时机、 122.买卖股票的最佳时机II
买卖股票主要是dp数组的定义和递推公式：
dp数组的定义：
dp[i][0]代表持有股票的状态的最大钱数目。
dp[i][1]代表不持有股票的状态的最大钱数目。
而根据这个定义，那么dp[i][0]包含两种状态：1、今天买入，变为持有
2、今天之前就已经买入了，今天不卖出，就是持有
同理dp[i][1]也包含两种状态：1、今天卖出，就是不持有了
2、今天之前已经卖出了，今天不买入，也是不持有
那么通过这个解释。就可以根据每种买卖股票的具体情况来进行递推公式的推导。
121、买卖股票的最佳时机
这道题就是选一天卖，选一天买
dp公式推导较为好理解，只买卖一次，最开始是0元。买入就变成了负数。
1）维持原状 2）改变状态
dp[i][0]=max（dp[i-1][0]，-price[i]）
dp[i][1]=max（dp[i-1][1]，dp[i-1][0]+price[i]）
遍历当然是从前向后遍历。
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};122.买卖股票的最佳时机II
这道题相对上一道题允许多次买卖，所以初始值就不一样了，不是0，需要根据前一个状态推导出来。
1）维持原状 2）改变状态
dp[i][0]=max（dp[i-1][0]，dp[i-1][1]-price[i]）
dp[i][1]=max（dp[i-1][1]，dp[i-1][0]+price[i]）
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; 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]);}return dp[len - 1][1];}
};
