题意：
        假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益。
              1. 你最多可以对该股票有k笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
              2. 如果不能获取收益，请返回0
              3. 假设买入卖出均无手续费

方法一：
三维dp

思路：
        dp[ i ][ j ][ k ]表示前 i 天最大交易次数是 j 时,k=0表示无股票状态,k=1表示有股票状态的最大收益。
        状态转移方程：
        
                        

 


class Solution {
public:
    int dp[1005][105][2]={0};
    //dp[i][j][k]表示前i天最大交易次数是j时,k=0表示无股票状态,k=1表示有股票状态的最大收益
    int maxProfit(vector<int>& prices, int k) {
        int n=prices.size();
        k=min(k,n/2);//最大交易次数
        
        //买入股票是一次交易
        for(int j=1;j<=k;j++){//初始化
            dp[1][j][1]=-prices[0];
        }
        
        for(int i=2;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];
    }
};


时间复杂度：
空间复杂度：


方法二：
二维dp

思路：
        用两个二维数组去代替方法一中的三维数组的第三维。
    

class Solution {
public:

    int a[1005][105]={0};//无股票状态
    int b[1005][105]={0};//有股票状态
    int maxProfit(vector<int>& prices, int k) {
        int n=prices.size();
        k=min(k,n/2);//最大交易次数
        
        //买入股票是一次交易
        for(int j=1;j<=k;j++){//初始化
            b[1][j]=-prices[0];
        }
        
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){//状态转移方程
                a[i][j]=max(a[i-1][j],b[i-1][j]+prices[i-1]);
                b[i][j]=max(b[i-1][j],a[i-1][j-1]-prices[i-1]);
            }
        }
        return a[n][k];
    }
};

时间复杂度：
空间复杂度：