【c++刷题笔记-动态规划】day42：188. 买卖股票的最佳时机 IV、309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

思路：奇数表示当前买股票后的钱的状态，偶数表示之前没买时钱的状态，并且每次购买都需要初始化

重点：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]);

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>>dp(n,vector<int>(2*k+1,0));
        //每次购买都需要初始化
        for(int i=1;i<2*k;i+=2){
            dp[0][i]=-prices[0];
        }
        for(int i=1;i<n;i++){
            for(int j=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]);
            }
        }
        return dp[n-1][2*k];
    }
};

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

思路：四种状态，0表示持有状态。1和2和在一起是未持有状态，拆分为保持卖出状态和今天就卖出状态。3表示冷冻期状态

重点：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];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>>dp(n,vector<int>(4,0));
        dp[0][0]=-prices[0];
        for(int i=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];//冷冻期状态
        }
        return max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]));
    }
};

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

思路：两个状态，卖出状态时扣除手续费

重点：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);

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<vector<int>>dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];
        for(int i=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);//昨天持有今天卖出是不持有状态
        }
        return max(dp[n-1][1],dp[n-1][0]);
    }
};

总结

股票问题，分清楚状态就很容易做了。持有状态分为前几天一直持有的状态、前几天不持有今天买入的状态。不持有状态分为前几天一直不持有状态，前几天持有今天卖出状态。