代码随想录一刷记录Day41——leetcode121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III

前言

之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！

leetcode121. 买卖股票的最佳时机

题目链接leetcode121. 买卖股票的最佳时机

思路

1. 确定dp数组（dp table）以及下标的含义
   dp[i][0] 表示第i天持有股票所得最多现金，dp[i][1] 表示第i天不持有股票所得最多现金
   注意：“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态
2. 确定递推公式
   如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来：
   第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
   第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
   那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
   如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来：
   第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
   第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
   同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
3. dp数组如何初始化
   由递推公式可知，其基础都是要从dp[0][0]和dp[0][1]推导出来。
   那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
   dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
4. 确定遍历顺序
   从前向后
5. 打印dp数组（debug用）

代码

classSolution{public:intmaxProfit(vector<int>&prices){intlen=prices.size();if(len==0)return0;vector<vector<int>>dp(len,vector<int>(2));dp[0][0]-=prices[0];dp[0][1]=0;for(inti=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]);}returndp[len-1][1];}};

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

题目链接leetcode122.买卖股票的最佳时机II

思路

本题和上一道121. 买卖股票的最佳时机最大的区别就是可以买卖多次，那么动规五部曲中唯一的区别在于递推公式中，第i天持有股票即dp[i][0]的推导。上一道题中因为只能买一次，所以第i天买入股票，所得现金就是0-prices[i]，而本题因为可以买卖多次，所以第i天买入股票时，可能之前就已经买过了，所以这一天所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格prices[i]，也就是dp[i-1][1] - prices[i]。

代码

classSolution{public:intmaxProfit(vector<int>&prices){intlen=prices.size();vector<vector<int>>dp(len,vector<int>(2,0));dp[0][0]-=prices[0];dp[0][1]=0;for(inti=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]);}returndp[len-1][1];}};

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

题目链接leetcode123.买卖股票的最佳时机III

思路

本题与前两道的区别在于之最多能买卖2次

1. 确定dp数组以及下标的含义
   一天一共就有五个状态，
   没有操作 （其实我们也可以不设置这个状态）
   第一次持有股票
   第一次不持有股票
   第二次持有股票
   第二次不持有股票
   dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
2. 确定递推公式
   dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
   dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
   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. 确定遍历顺序
   从前向后

代码

classSolution{public:intmaxProfit(vector<int>&prices){if(prices.size()==0)return0;vector<vector<int>>dp(prices.size(),vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(inti=1;i<prices.size();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]);}returndp[prices.size()-1][4];}};