当题目中 k k k大于表格数量的 1 2 \frac{1}{2} 21​的时候，就相当于无限制了，这个时候采用贪心算法更好。否则就得用动态规划。

根据上篇介绍动态规划设计的方法， d p ( p , k ) dp(p,k) dp(p,k)应该代表着当数组为p时候最多完成k笔交易，所能获得的最大利润。然后找这个问题中股民遇到的选择情景，股民每一天都可以选择买与不买，卖与不卖，通过这些选择来使自己利益最大化，需要注意的是买与不买是在自己不持股票的状态下，卖与不卖是在自己持股的状态下。所以每一天的两种状态都在dp范围内。

假设股民在i-1天之前在两种情况下都已经是做出了自己最优的选择了，那么在第i天我们应该如何做出抉择呢？
我们假设 d p ( i , j ) dp(i,j) dp(i,j)代表包括第i天的前i天的股票给最大j笔交易机会，且当前不持股情况下，最大利润能是多少。很明显这和原问题是同样的结构。 这里包含了第i天的选择操作。
我们再假设 h o l d ( i , j ) hold(i,j) hold(i,j)代表包括第i天的前i天的股票给最大j笔交易机会，且当前持股情况下，你目前的最大金钱数能是多少。这里和上面的区别在于，在这之前你是花了前买了一个股票的，至于是第i天买的还是更早买的，无所谓了。

我们要让股民利益最大化，在第i天要做出选择：

• 在当天不持股的情况下，说明要么他本来就不持股，要么说明他今天卖掉了自己的股票,消耗了一次交易机会，我们选择一个能让他利益最大的情况
  d p ( i , j ) = m a x ( d p ( i − 1 , j ) , h o l d ( i − 1 , j − 1 ) + p [ i ] ) dp(i,j)=max(dp(i-1,j),hold(i-1,j-1)+p[i]) dp(i,j)=max(dp(i−1,j),hold(i−1,j−1)+p[i])
• 在当天持股的情况下，说明要么他本来就持股，要么说明他今天买了股票，我们选择一个能让他利益最大的情况
  h o l d ( i , j ) = m a x ( h o l d ( i − 1 , j ) , d p ( i − 1 , j ) − p [ i ] ) hold(i,j)=max(hold(i-1,j),dp(i-1,j)-p[i]) hold(i,j)=max(hold(i−1,j),dp(i−1,j)−p[i])

写出表达式后我们要计算初始值：
d p ( 0 , j ) = 0 , j = 0 , 1 , 2... k h o l d ( 0 , j ) = − p [ 0 ] , j = 0 , 1 , 2... k d p ( i , 0 ) = 0 , i = 0 , 1 , 2... p . s i z e − 1 dp(0,j)=0,j=0,1,2...k\\ hold(0,j)=-p[0],j=0,1,2...k\\ dp(i,0)=0,i=0,1,2...p.size-1\\ dp(0,j)=0,j=0,1,2...khold(0,j)=−p[0],j=0,1,2...kdp(i,0)=0,i=0,1,2...p.size−1

贪心比dp要容易，当 k k k大于表格数量的 1 2 \frac{1}{2} 21​的时候，我们认为是无限制买卖。所以只要是涨价，我们都买。把原数列差分，然后把大于0的都加起来就是。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp,hold;
        if(prices.size()==0)return 0;
        if(k>prices.size()/2){
            return greedy(prices);
        }
        dp=vector<vector<int>>(prices.size(),vector<int>(k+1,0));
        hold=vector<vector<int>>(prices.size(),vector<int>(k+1,0));

        for(int i=0;i<=k;i++){
            hold[0][i]=-prices[0];
        }
        for(int i=1;i<prices.size();i++){
            hold[i][0]=max(hold[i-1][0],-prices[i]);
        }
         
        for(int i=1;i<prices.size();i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=max(dp[i-1][j],hold[i-1][j-1]+prices[i]); 
                hold[i][j]=max(hold[i-1][j],dp[i-1][j]-prices[i]);
            }
        }

        return dp[prices.size()-1][k];
    }

    int greedy(vector<int>& prices){
        int ans=0;
        for(int i=0;i<prices.size()-1;i++){
            ans+=max(0,prices[i+1]-prices[i]);
        }
        return ans;
    }
};