前言之前就有刷代码随想录但奈何总是三天打鱼两天晒网而且刷的也很囫囵吞枣于是乎决定参加代码随想录训练营准备精刷一遍希望自己能坚持下去结营后自己的算法水平能更上一个level冲ingleetcode121. 买卖股票的最佳时机题目链接leetcode121. 买卖股票的最佳时机思路确定dp数组dp table以及下标的含义dp[i][0] 表示第i天持有股票所得最多现金dp[i][1] 表示第i天不持有股票所得最多现金注意“持有”“持有”不代表就是当天“买入”也有可能是昨天就买入了今天保持持有的状态确定递推公式如果第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]);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;确定遍历顺序从前向后打印dp数组debug用代码classSolution{public:intmaxProfit(vectorintprices){intlenprices.size();if(len0)return0;vectorvectorintdp(len,vectorint(2));dp[0][0]-prices[0];dp[0][1]0;for(inti1;ilen;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(vectorintprices){intlenprices.size();vectorvectorintdp(len,vectorint(2,0));dp[0][0]-prices[0];dp[0][1]0;for(inti1;ilen;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次确定dp数组以及下标的含义一天一共就有五个状态没有操作 其实我们也可以不设置这个状态第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票dp[i][j]中 i表示第i天j为 [0 - 4] 五个状态dp[i][j]表示第i天状态j所剩最大现金。确定递推公式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]);dp数组如何初始化dp[0][0] 0; dp[0][1] -prices[0]; dp[0][2] 0; dp[0][3] -prices[0]; dp[0][4] 0;确定遍历顺序从前向后代码classSolution{public:intmaxProfit(vectorintprices){if(prices.size()0)return0;vectorvectorintdp(prices.size(),vectorint(5,0));dp[0][1]-prices[0];dp[0][3]-prices[0];for(inti1;iprices.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];}};