代码随想录算法训练营第四十二天|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,vector<int>&prices){if(prices.size()==0)return0;vector<vector<int>>dp(prices.size(),vector<int>(2*k+1,0));for(intj=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(inti=1;i<prices.size();i++){for(intj=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+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(vector<int>&prices){intn=prices.size();if(n==0)return0;vector<vector<int>>dp(n,vector<int>(4,0));dp[0][0]-=prices[0];// 持股票for(inti=1;i<n;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(vector<int>&prices,intfee){intn=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));dp[0][0]-=prices[0];// 持股票for(inti=1;i<n;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)