121. 买卖股票的最佳时机
题目链接/文章讲解/视频讲解：https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html
1.代码展示
//121.股票的最佳买卖时机
int maxProfit(vector<int>& prices) {//step1.构建dp数组//dp[i][0]的含义是当前未持有股票时的余额//dp[i][1]的含义是当前持有股票的余额vector<vector<int>> dp(prices.size(), vector<int>(2, 0));if (prices.size() == 1) {return 0;}//step2 状态转移方程//未持有，可能是前一天的状态，也可能是今天卖掉的//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])//持有，可能是前一天的状态，也可能是今天买的//dp[i][1] = max(dp[i - 1][1], -prices[i])//step3 初始化dp数组dp[0][0] = 0;dp[0][1] = -prices[0];//step4 开始遍历for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], -prices[i]);}return dp[prices.size() - 1][0];}2.本题小节
思考：本题的需要明确的是状态转移方程的由来，每一天需要统计是否持有股票时的金额，因此每一天是有两个状态的，持有和不持有，dp[i][0]的含义是第i+1天没有持有股票时的金额，dp[i][1]的含义是第i+1天持有股票时的金额，通过分析可以知道，dp[i][0]由两种情况，一种是前一天就没有持有股票，另外一种情况是今天卖掉股票，因此对这两种情况取最大值，因此第i+1状态转移公式如代码中所示；同理，dp[i][1]也是两种情况，情况一是前一天就买了，情况二是当前天才买，注意当前天才买的话为-price[i]，因为只能买卖一次，因此买的话就直接是-price[i]。最后返回未持股票的最后一位为答案。
基本思路：补充一下，注意初始化。
122.买卖股票的最佳时机II
题目链接/文章讲解/视频讲解：代码随想录
1.代码展示
//122.股票的最佳买卖时机Ⅱ
int maxProfit(vector<int>& prices) {//step1.构建dp数组//dp[i][0]的含义是当前未持有股票时的余额//dp[i][1]的含义是当前持有股票的余额vector<vector<int>> dp(prices.size(), vector<int>(2, 0));if (prices.size() == 1) {return 0;}//step2 状态转移方程//未持有，可能是前一天的状态，也可能是今天卖掉的//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])//step3 初始化dp数组dp[0][0] = 0;dp[0][1] = -prices[0];//step4 开始遍历for (int i = 1; i < prices.size(); 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[prices.size() - 1][0];}2.本题小节
思考：本题与上一题的区别是可以买卖多次，每次依然只能持有一张股票，因此也是只需要判断所持有或者不持有的状态，重点依然是状态转移方程，dp[i][0]与dp[i][1]的含义与上题是一样的，分析后发现，dp[i][0]与上一题一样，而dp[i][1]的第二种情况要使用上一天没买入来减，因为每次只能持有一张股票，因此上一天没买股票，当前天才能买股票，其他的都是一样的。
