代码随想录算法训练营第四十二天|LeetCode 188 买卖股票的最佳时机 IV、LeetCode 309 最佳买卖股票时机含冷冻期、LeetCode 714 买卖股票的最佳时机含手续费

参考文章均来自代码随想录LeetCode 188 买卖股票的最佳时机 IV参考文章链接给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1 输入k 2, prices [2,4,1] 输出2 解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。 示例 2 输入k 2, prices [3,2,6,5,0,3] 输出7 解释在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4 。 随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。本题变为至多k次交易使用二维数组 dp[i][j] 第i天的状态为j所剩下的最大现金是dp[i][j]j的状态表示为0 表示不操作1 第一次买入2 第一次卖出3 第二次买入4 第二次卖出…除了0以外偶数就是卖出奇数就是买入。题目要求是至多有K笔交易那么j的范围就定义为 2 * k 1 就可以了。第0天没有操作这个最容易想到就是0即dp[0][0] 0;第0天做第一次买入的操作dp[0][1] -prices[0];第0天做第一次卖出的操作可以理解为当天买入当天卖出所以dp[0][2] 0;第二次买入依赖于第一次卖出的状态其实相当于第0天第一次买入了第一次卖出了然后在买入一次第二次买入那么现在手头上没有现金只要买入现金就做相应的减少。所以第二次买入操作初始化为dp[0][3] -prices[0];第二次卖出初始化dp[0][4] 0;所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]classSolution{public:intmaxProfit(intk,vectorintprices){if(prices.size()0)return0;vectorvectorintdp(prices.size(),vectorint(2*k1,0));for(intj1;j2*k;j2){dp[0][j]-prices[0];}for(inti1;iprices.size();i){for(intj0;j2*k-1;j2){dp[i][j1]max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2]max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}returndp[prices.size()-1][2*k];}};时间复杂度: O(n * k)其中 n 为 prices 的长度空间复杂度: O(n * k)LeetCode 309 最佳买卖股票时机含冷冻期参考文章链接力扣题目链接加入冷冻期后状态会更复杂一点具体有四个状态状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有不持有股票状态这里就有两种卖出股票状态状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作状态三今天卖出股票状态四今天为冷冻期状态但冷冻期状态不可持续只有一天达到买入股票状态状态一即dp[i][0]有两个具体操作操作一前一天就是持有股票状态状态一dp[i][0] dp[i - 1][0]操作二今天买入了有两种情况前一天是冷冻期状态四dp[i - 1][3] - prices[i]前一天是保持卖出股票的状态状态二dp[i - 1][1] - prices[i]那么dp[i][0] max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);达到保持卖出股票状态状态二即dp[i][1]有两个具体操作操作一前一天就是状态二操作二前一天是冷冻期状态四dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);达到今天就卖出股票状态状态三即dp[i][2] 只有一个操作昨天一定是持有股票状态状态一今天卖出即dp[i][2] dp[i - 1][0] prices[i];达到冷冻期状态状态四即dp[i][3]只有一个操作昨天卖出了股票状态三dp[i][3] dp[i - 1][2];classSolution{public:intmaxProfit(vectorintprices){intnprices.size();if(n0)return0;vectorvectorintdp(n,vectorint(4,0));dp[0][0]-prices[0];// 持股票for(inti1;in;i){dp[i][0]max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));dp[i][1]max(dp[i-1][1],dp[i-1][3]);dp[i][2]dp[i-1][0]prices[i];dp[i][3]dp[i-1][2];}returnmax(dp[n-1][3],max(dp[n-1][1],dp[n-1][2]));}};时间复杂度O(n)空间复杂度O(n)LeetCode 714 买卖股票的最佳时机含手续费参考文章链接力扣题目链接本题和原题差不多 加一个手续费即可classSolution{public:intmaxProfit(vectorintprices,intfee){intnprices.size();vectorvectorintdp(n,vectorint(2,0));dp[0][0]-prices[0];// 持股票for(inti1;in;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]-fee);}returnmax(dp[n-1][0],dp[n-1][1]);}};时间复杂度O(n)空间复杂度O(n)