强烈推荐仔细阅读这篇题解，可能会对大家有所启发

原创不易，觉得不错可以点个赞

描述

题目描述

给我们一个股票每天的价钱，我们最多可以进行$kk$次操作，然后我们一次操作结束前，我们不能进行其他操作，问我们最后可以最多赚多少钱

样例解释

因为前两个样例解释的已经是非常的详细了，这里不过多赘述我们的前两个样例，这里简单解释一下第三个样例

样例输入

[9,8,4,1],4

这里我们可以很容易发现，这个数组是一个递减的数组，只要我们买了股票，就一定是跌的，所以我们什么也不动弹就是最优的解决方案了

样例输出

0

这里提出几个要注意的点

第一个： 我们的$kk$，只要取$min(n\mathrm{/}2,k)min(n\; /\; 2,\; k)$即可

理由如下：这个是因为，我们最多是有$n\mathrm{/}2n\; /\; 2$次的操作，因为我们每次操作代表的是，我们买入然后卖出，这是一个操作，这里我们可以想一下，我们一次操作，是要对于两天操作，这里有同学可能会有一个疑问就是，我为什么不可以一天卖出再买入，我们可以想一下，卖出再买入，相当于费用是$00$，并且这个一定不是最优解，分为两种情况，以前买入点比当前点高，另一个买入点比当前点低，无论如何都是不划算的

第二个：我们最后一天的时候一定是手里没有股票的时候，我们才是最优解

理由如下：我们想一下，到了最后一天，我们手里如果还有股票，那么我如果我们卖出去可以获利$xx$，如果我们不卖出去，那么我们就什么获利都没有，就算是卖出去我们总共还是亏的，那我们是可以少亏一点的

第三个：这里我们以买入点作为一次操作

这里强调这点是因为，我们接下来的代码会基于这个来进行，我们的$kk$是根据我们的这个什么时候买入，来进行增加，当然大家也可以把卖出点作为变化点来进行操作

题解

解法一：三维DP

解题思路：

强调：这里这个是最为暴力的情况，接下来的解法二和解法三都是基于我们这个解法来进行优化的

首先我们想一下，我们应该用一个数组来表示我们的每次的答案

第一点： 考虑我们有几个维度

首先我们有天数，操作次数，当前股票的状态（是在手里，还是没在手里） 这样我们就是有三个维度

第二点： 考虑每一个维度的意义

那么我们开始划分 第一个维度就是我们的天数，我们用$ii$来表示 第二个维度就是我们的操作次数，我们用$jj$来表示 第三个维度就是我们当前的状态, 我们用$zz$来表示 那么我们最终得到的就是这么一个状态

第三点： 考虑每一个维度构成的最终的数组，如何得到

我们考虑这么一个问题，如果我们

第$ii$天不持有股票，那么我们这天是不是可以由$i-1i\; -\; 1$得到，那么我们$i-1i\; -\; 1$天有两种情况

第一种就是，我们第$i-1i\; -\; 1$天我们也没有持有股票

第二种就是我们第$i-1i\; -\; 1$持有股票，那么我们第$ii$天不持有股票的原因就是因为我们在这天卖出去了，那么我们就是要用第$i-1i\; -\; 1$持有股票的钱加上我们今天股票卖出的价格，二者我们取一个最高值

则我们有了如下的一个状态转移方程

$dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);dp[i][j][0]\; =\; max(dp[i\; -\; 1][j][0],\; dp[i\; -\; 1][j][1]\; +\; prices[i]);$

然后我们如果第$ii$天手里持有股票，那么我们这天也是由$i-1i\; -\; 1$天得到，那么我们还是分为两种情况

第一种就是我们$i-1i\; -\; 1$天手里也是有股票的，那么我们的状态不变

第二种就是我们$i-1i\; -\; 1$天手里没有股票，说明我们是在$ii$买入的股票，那么我们就是得花掉钱

则我们有如下的状态转移方程

$dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);dp[i][j][1]\; =\; max(dp[i\; -\; 1][j][1],\; dp[i\; -\; 1][j\; -\; 1][0]\; -\; prices[i]);$

最后我们把第一天没有股票情况为$00$, 有股票就是花费第一天的价钱$prices[0]prices[0]$

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
//         获取数组长度
        if (n <= 1) return 0;
//         如果数组只有1天没有机会操作
        k = min(n / 2, k);
//         我们k的取值范围，根据我前面描述的
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2)));
//         开辟的三位数组
        for (int i = 0; i <= k; i++) {
            dp[0][i][0] = 0, dp[0][i][1] = -prices[0];
        } 
//         对我们第一天进行一个初始值赋值
        for (int i = 1; i < n; i++) {
//             第1到n天
            for (int j = 1; j <= k; j++) {
//                 我们对操作数进行枚举
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
//                 dp的状态转移方程
            }
        }
        return dp[n - 1][k][0];
//         最后全部卖出股票的结果
    }
};

时空复杂度

时间复杂度： $O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

理由如下： 因为我们时间复杂度的瓶颈在于我们的双层循环，所以复杂度是$O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

空间复杂度： $O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

理由如下： 因为我们开辟的三维数组是$(n\ast min(n\mathrm{/}2,k))\ast 2(n\; *\; min(n\; /\; 2,\; k))\; *\; 2$的，复杂度中不带常数，所以最后是$O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

解法二：二维DP

解题思路

其实我们可以很容易的发现，其实我们刚才的第三维，完全可以用两个数组代替，一个代表我们的$00$一个代表$11$

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
//         获取数组长度
        if (n <= 1) return 0;
//         如果数组只有1天没有机会操作
        k = min(n / 2, k);
//         我们k的取值范围，根据我前面描述的
        vector<vector<int>> lose(n, vector<int>(k + 1, 0)), get(n, vector<int>(k + 1, -prices[0]));
//         二维数组，一个是代表原先的0，一个代表的是原先1
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                lose[i][j] = max(lose[i - 1][j], get[i - 1][j] + prices[i]);
                get[i][j] = max(get[i - 1][j], lose[i - 1][j - 1] - prices[i]);
            }
        }
        return lose[n - 1][k];
    }
};

时空复杂度

时间复杂度： $O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

理由如下： 因为我们时间复杂度的瓶颈在于我们的双层循环，所以复杂度是$O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

空间复杂度： $O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

理由如下： 因为我们开辟了两个二维数组是$(n\ast min(n\mathrm{/}2,k))\ast 2(n\; *\; min(n\; /\; 2,\; k))\; *\; 2$的，复杂度中不带常数，所以最后是$O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

解法三：一维DP

解题思路

其实我们再仔细思考，我们会发现这么一个问题，我们其实每步只跟前一天有关系，那么我们其实我们可以把时间的这个维度也给压缩,然后这里为什么正确呢，其实就是因为，我们会有一步操作，我们在转移的时候，可以理解为是在当天买入和卖出，对我们最后的结果是没有任何影响的

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
//         获取数组长度
        if (n <= 1) return 0;
//         如果数组只有1天没有机会操作
        k = min(n / 2, k);
//         我们k的取值范围，根据我前面描述的
        vector<int> lose(k + 1, 0), get(k + 1, -prices[0]);
//         一个是我们之前代表0，一个代表1
        for (int i = 1; i < n; i++) {
//             n天
            for (int j = 1; j <= k; j++) {
//                 k次操作  
                lose[j] = max(lose[j], get[j] + prices[i]);
                get[j] = max(get[j], lose[j - 1] - prices[i]);
//                 状态转移方程
            }
        }
        return lose[k];
    }
};

时空复杂度

时间复杂度： $O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

理由如下： 因为我们时间复杂度的瓶颈在于我们的双层循环，所以复杂度是$O(n\ast min(n\mathrm{/}2,k))O(n\; *\; min(n\; /\; 2,\; k))$

空间复杂度： $O(min(n\mathrm{/}2,k))O(min(n\; /\; 2,\; k))$

理由如下： 我们开辟了两个长度为$kk$的数组，而我们的$kk$是$min(k,n\mathrm{/}2)min(k,\; n\; /\; 2)$，这步在最前面讲过为什么，所以我们的空间复杂度是$O(min(n\mathrm{/}2,k))O(min(n\; /\; 2,\; k))$

最后贴一个代码排行