leetcode 股票问题全序列

1 只允许一次交易，121题，买卖股票的最佳时机

class Solution {
    /*
    给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
    */
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2){
            return 0;
        }
        int maxP=0x80000000;
        int minPrice=prices[0];
        for(int i=1;i<prices.size();i++){
            if(minPrice>prices[i]){
                minPrice=prices[i];
            }
            maxP=max(maxP,prices[i]-minPrice);
        }
        return maxP;
    }
};

2 可以交易多次，122题， 买卖股票的最佳时机2

class Solution {
    /*
    题目：
    给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
题解：
贪心
因为不限制交易次数，只要今天价格比昨天高，就交易，利润为正累加，最后的和就是最大的利润
    */
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2){
            return 0;
        }
        int res=0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i+1]>prices[i]){
                res+=(prices[i+1]-prices[i]);
            }
        }
        return res;
    }
};

3 最多2次交易，123题， 买卖股票的最佳时机3

class Solution {
    /*
    给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    题解：
    动态规划：
    dp[i][j] 中 i 表示第 i 天，j为 [0?4]五个状态，dp[i][j]表示第i天状态j所得最大现金
    j=0无操作 =1第一次买入，=2第一次卖出，=3第二次买入，=4第二次卖出
        |buy|buy|sell|sell|sell|buy|buy|
        |---|---|----|----|----|---|---|
                |    |
                  当天
                 第一次 保持
                  卖出
    */
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<1){
            return 0;
        }
        // dp[i][j]表示第i天状态j所得最大现金
        vector<vector<int>>dp(prices.size(),vector<int>(5,0));
        // init
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0;//第一天就卖出 相当于第一次买入后又卖出了
        dp[0][3]=-prices[0];
        // 第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，
        // 然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少
        dp[0][4]=0;
        for(int i=1;i<prices.size();i++){
            // 1. 第i天无操作,则之前也是没有操作
            dp[i][0]=dp[i-1][0];
            // 2. 第i天第一次买入
            dp[i][1]=max(
                dp[i-1][1],//前一天买入，当天保持
                dp[i-1][0]-prices[i]//当天买入，前一天还是没有操作
            );
            // 3. 第i天第一次卖出
            dp[i][2]=max(
                dp[i-1][2],//前一天卖出，当天保持
                dp[i-1][1]+prices[i]//当天第一次卖出，前一天还是第一次买入
            );
            // 4. 第i天第二次买入
            dp[i][3]=max(
                dp[i-1][3],//前一天买入，当天保持
                dp[i-1][2]-prices[i]//当天买入，前一天还是第一次卖出
            );
            // 5. 第i天第二次卖出
            dp[i][4]=max(
                dp[i-1][4],//前一天卖出，当天保持
                dp[i-1][3]+prices[i]//当天第二次卖出，前一天还是第二次买入
            );
        }
        return dp[prices.size()-1][4];
    }
};

4. 最多k次交易，188题，买卖股票的最佳时间4

class Solution {
    /*
    题目：
    给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
    题解：
    定义一个三维数组dp[n][k][2]这里n表示天数，
    dp[i][j][0]：表示第i天交易了j次时卖出后的累计最大利润
    dp[i][j][1]：表示第i天交易了j次时买入后的累计最大利润
    1. 第一次买入：要么前一天买入后保持，要么从初始态第一次买入
        dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])
       第一次卖出（注意已经完成一次交易这里j=1）：要么前一天卖出后保持，要么从前一天第一次买入后，当天卖出
        dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])
    2. 第二次买入：要么前一天买入后保持，要么从前一天第一次卖出后当天第二次买入
        dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])
       第二次卖出（注意已经完成一次交易这里j=2）：要么前一天卖出后保持，要么从前一天第二次买入后，当天卖出
        dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])
    ...
    j. 第j次买入：要么前一天买入后保持，要么从前一天第j-1次卖出后当天第二次买入
        dp[i][j-1][1]=max(dp[i-1][j-1][1],dp[i-1][j-1][0]-prices[i])
       第二次卖出（注意已经完成一次交易这里j=j）：要么前一天卖出后保持，要么从前一天第j次买入后，当天卖出
        dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])
    init
      for(int i = 0; i <= k; ++i) {
          dp[0][i][0] = 0;// 第一天，不管交易多少次，卖出都是0收入
          dp[0][i][1] = -prices[0]; // 第一天，不管交易多少次，买入的收入是-prices[0]
      }
    三维数组太高了进行压缩，从上面DP公式可以知道，可以去掉天数纬度，用二维数组dp[k][2]来表示
    则有：
    dp[j-1][1]=max(dp[j-1][1],dp[j-1][0]-prices[i])
    dp[j][0]=max(dp[j][0],dp[j-1][1]+prices[i])
    */
public:
    int maxProfit122(vector<int>&prices){
        // 不限制次数的交易
        if(prices.size()<2){
            return 0;
        }
        int res=0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i+1]>prices[i]){
                res+=prices[i+1]-prices[i];
            }
        }
        return res;
    }
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(k>=n){
            // 类似122题，不限制次数的交易
            return maxProfit122(prices);
        }
        // dp[j][z]交易第j次z=0时候卖出后的收益，
        // dp[j][z]交易第j次z=1时候买入后的收益
        vector<vector<int>>dp(k+1,vector<int>(2,0));
        // init 根据三维降级而得,第一天
        for(int i=0;i<k;i++){
            dp[i][0]=0;//第一天无论交易多少次，卖出后的收益都是0
            dp[i][1]=-prices[0];//第一天无论交易多少次，买入后的收益都是-price[0]
        }
        for(int i=1;i<prices.size();i++){
            for(int j=1;j<=k;j++){
                dp[j-1][1]=max(dp[j-1][1],dp[j-1][0]-prices[i]);
                dp[j][0]=max(dp[j][0],dp[j-1][1]+prices[i]);
            }
        }
        return dp[k][0];
    }
};