DP状态机——股票问题

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        int dp[n+1][k+1][2];
        for(int i=0;i<=k;i++){//第0天的情况
            dp[0][i][0]=0;
            dp[0][i][1]=-1e9;
        }
        for(int i=0;i<=n;i++){//交易次数是0的情况
            dp[i][0][0]=0;
            dp[i][0][1]=-1e9;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
            }
        }
        return dp[n][k][0];
    }
};

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

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