代码随想录算法训练营第五十三天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、总结

本文主要是介绍代码随想录算法训练营第五十三天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第五十三天

309.最佳买卖股票时机含冷冻期

题目链接：309.最佳买卖股票时机含冷冻期

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size(),vector<int>(4,0));dp[0][0] = 0;//不操作dp[0][1] = -prices[0];//持有dp[0][2] = 0;//不持有dp[0][3] = 0;//冷冻期for(int i =1;i<prices.size();i++){dp[i][0] = 0;dp[i][1] = max(dp[i-1][1],dp[i-1][3]-prices[i]);dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);dp[i][3] = dp[i-1][2];}return dp[prices.size()-1][2];}
};

---

714.买卖股票的最佳时机含手续费

题目链接：714.买卖股票的最佳时机含手续费

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>>dp(prices.size(),vector<int>(3,0));dp[0][0] = 0;//不操作dp[0][1] = -prices[0];//持有dp[0][2] = 0;//不持有for(int i =1;i<prices.size();i++){dp[i][0] = 0;dp[i][1] = max(dp[i-1][1],dp[i-1][2]-prices[i]);dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]-fee);}return dp[prices.size()-1][2];}
};

---

总结

买卖股票的dp数组dp[i][j]，i是第i天的价格，有j是状态，根据题目需要分为持有，不持有，第k次持有，第k次卖出后（买入前），冷却期等。需要了解当前状态可能是由前一天的哪种状态转变过来的。

1. 买卖一次：
   不持有=保持前一天的不持有或当天卖出

   dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
   

   持有=保持前一天的持有或者当天买入

   dp[i][1] = max(dp[i-1][1],0-prices[i]);
   

2. 买卖多次：
   不持有=保持前一天的不持有或当天卖出

   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]);
   

3. 只能买卖2次:
   不操作：

   dp[i][0] = 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]);
   

4. 只能买卖k次：
   总共状态有2k种，第k次持有或第k次不持有

    if (j % 2 == 1) //奇数持有dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);else  //偶数不持有dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
   

5. 含冷冻期：
   不操作：

   dp[i][0] = 0;
   

   持有：

   dp[i][1] = max(dp[i-1][1],dp[i-1][3]-prices[i]);            
   

   不持有：

   dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
   

   冷冻期：

   dp[i][3] = dp[i-1][2];
   

6. 含手续费：
   状态和2相同，卖出时多减一份手续费即可
   持有：

   dp[i][1] = max(dp[i-1][1],dp[i-1][2]-prices[i]);
   

   不持有：

   dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]-fee);           
   

这篇关于代码随想录算法训练营第五十三天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---