代码随想Day51 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

本题多了一个冷冻期，就需要把不持有股票的状态拆分，这样才能顺利进行递推。

动态数组定义dp：

dp[0]：持有股票的最大金额

dp[1]：保持不持有股票的状态的最大金额；

dp[2]：卖出股票的最大金额；

dp[3]：冷冻期的最大金额；

递推公式：

dp[i][0]：不持有股票有三种可能，分别是前一天就持有股票，前一天是保持不持有股票今天买入，以及前一天是冷冻期今天买入，取三者的最大值；

dp[i][1]：保持不持有股票的状态的两种可能：前一天就是不持有状态以及前一天是冷冻期状态；

dp[i][2]：卖出股票：前一天持有今天卖出；

dp[i][3]：冷冻期只能是前一天卖出股票得到；

初始化：

只有dp[0][0]=-prices[0]，其他都是0，本身状态无意义，可以通过递推公式反推出来需要的初始值。

遍历顺序：

从i等于1开始向后；

详细代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //不持有股票需要进行拆分，否则没法分辨
        //0:持有股票
        //1：保持不持有股票的状态
        //2: 卖出股票
        //3: 冷冻期
        vector<vector<int>>dp(prices.size(),vector<int>(4,0));
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.size();i++)
        {
            dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-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];
        }
        int size=prices.size()-1;
        return max(dp[size][1],max(dp[size][2],dp[size][3]));

    }
};

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

这道题和无限次买卖股票几乎一样，只需要在卖出股票的时候减去手续费就可以，不再进行详细分析，直接附上代码：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        //只需要在卖出的时候减去手续费
        //持有股票0； 不持有股票1
        vector<vector<int>>dp(prices.size(),vector<int>(2,0));
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.size();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);
        }
        return dp[prices.size()-1][1];

    }
};

代码随想录-股票系列总结