买卖股票的最佳时机专题（动态规划）

一. 买卖一次(简单)

dp[i]表示第i天卖出时的最大值，可以用滚动变量优化

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(n+1);
        int min_= INT_MAX;
        for(int i=0;i<n;i++){
            dp[i+1]=max(dp[i],prices[i]-min_);
            min_=min(min_,prices[i]);//记录已经遍历的最小值
        }
        return dp[n];
    }
};

二. 买卖无数次（中等）

dp[i][j]表示第i天持股状态j下的最大收益，可以用滚动变量优化

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][j]表示第i天持股状态j下的最大收益
        int n = prices.size();
        int dp[n+1][2];
        dp[0][0] = 0; dp[0][1] = -prices[0];//边界条件
        for(int i=0;i<n;i++){
            dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i]);//第i天不持股
            dp[i+1][1] = max(dp[i][1],dp[i][0]-prices[i]);//第i天持股
        }
        return dp[n][0];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {   
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

三. 最多进行两笔交易（困难）

dp[i][j][k]表示第i天持有状态j交易次数k下的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();//将买入视作进行了一次交易，然后卖出就可以从当前买入状态进行转移
        int dp[n+1][2][3];//dp[i][j][k]表示第i天持有状态j交易次数k下的最大利润
        for(int i=0;i<n;i++)
            dp[i+1][0][0] = 0;//多余边界初始化0
        for(int j=0;j<2;j++){
            dp[0][0][j+1] = 0;//多余边界初始化0
            dp[0][1][j+1] = -prices[0];//这里直接给初值，没必要再使用多余空间
        }
        for (int i = 0; i < n; i++) {
            for(int j=0;j<2;j++){
                dp[i+1][1][j+1] = max(dp[i][1][j+1],dp[i+1][0][j]-prices[i]);//第j次买入
                dp[i+1][0][j+1] = max(dp[i][0][j+1],dp[i+1][1][j+1]+prices[i]);//第j次卖出
            }
        }
        return dp[n][0][2];
    }
};

四. 最多进行k笔交易（困难）

dp[i][j][k]表示第i天持有状态j交易次数k下的最大利润

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();//将买入视作进行了一次交易，然后卖出就可以从当前买入状态进行转移
        int dp[n+1][2][k+1];//dp[i][j][k]表示第i天持有状态j交易次数k下的最大利润
        for(int i=0;i<n;i++)
            dp[i+1][0][0] = 0;//多余边界初始化0
        for(int j=0;j<k;j++){
            dp[0][0][j+1] = 0;//多余边界初始化0
            dp[0][1][j+1] = -prices[0];//这里直接给初值，没必要再使用多余空间
        }
        for (int i = 0; i < n; i++) {
            for(int j=0;j<k;j++){
                dp[i+1][1][j+1] = max(dp[i][1][j+1],dp[i+1][0][j]-prices[i]);//第j次买入
                dp[i+1][0][j+1] = max(dp[i][0][j+1],dp[i+1][1][j+1]+prices[i]);//第j次卖出
            }
        }
        return dp[n][0][k];
    }
};

五. 买卖无限次含冷冻期一天

dp[i][j]表示第i天状态为j的情况下最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n+1][3];
        for(int i=0;i<3;i++)
            dp[0][i] = 0;//多余边界初始化0
        dp[0][0] = -prices[0]; //直接赋初值，使能进入循环
        for (int i = 0; i < n; ++i) {
            dp[i+1][0] = max(dp[i][0],dp[i][2]-prices[i]);//持有股票状态
            dp[i+1][1] = dp[i][0] + prices[i];//卖出股票且在冷冻期
            dp[i+1][2] = max(dp[i][2], dp[i][1]);//卖出股票且不在冷冻期
        }
        return max(dp[n][1],dp[n][2]);
    }
};

六.买卖无限次含手续费

与题二基本一致

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        //dp[i][j]表示第i天持股状态j下的最大收益
        int n = prices.size();
        int dp[n+1][2];
        dp[0][0] = 0; dp[0][1] = -prices[0]-fee;//边界条件
        for(int i=0;i<n;i++){
            dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i]);//第i天不持股
            dp[i+1][1] = max(dp[i][1],dp[i][0]-prices[i]-fee);//第i天持股
        }
        return dp[n][0];
    }
};