题目分析

这个题目有很多人都总结了各个版本的股票问题，可以持多股的问题，有冷却期的问题，可以重复交易的问题，要手续费的问题等等，今天遇到的这个问题是最多可以交易k次的题目。这类问题的统一解法都是动态规划思路。

动态规划

我们做动态规划问题的核心是找到状态转移方程。这个题目很明显，我们用三维DP进行求解，第一维大小是prices.size()，说明此时到哪一天，第二维的大小是k，说明此时交易了多少次，第三位的大小为2，此时手里是否还有股票。当然小伙伴们觉得复杂可以使用两个二维DP，就是将第三个维度进行拆分。

这里我们定义卖出股票的时候记为交易了一笔，我们先思考，dp[i][j][0]是什么意思呢？代表第i天，已经交易了j次，手中没有股票的最大收益，可能是昨天就已经交易了j次，手中没有股票，今天没有买入。也可能是昨天交易了j - 1次，手中有一支股票，今天卖出去了，因此今天手中没有股票。
$$dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i])$$

同理可得dp[i][j][1]是什么意思呢？代表第i天，已经交易了j次，手中有一支股票，可能是昨天就交易了j次，有一只股票，没有卖出，也可能是昨天已经交易了j次，手里没有股票，在今天买入了一只股票。
$$dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i])$$

**初始值我们只当手中没有股票的时候，最小收益为0，因为一次都不买即可，当手中有股票的时候，初始值都赋值为无穷小。然后给第一天赋值即可dp[0][0][0] = 0，dp[0][0][1] = -prices[0]。说明第一天没有买股票的时候收益为0，买了股票，收益为-prices[0]**。

我们分析算法的时间复杂度，第一层循环n次，第二层循环k次，但是题目中k是1e9量级的，因此直接无法通过，我们再观察prices的长度最大为1000。而且最后手中一定是没有股票的，如果手中最后留有股票，我们可以不进行最后一次买入。即使一天买入，一天卖出，最大的交易次数也最多为prices.size() / 2。

算法的**时间复杂度为$O(n \times min(n, k))$，空间复杂度为$O(n \times min(n, k))$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int length = prices.size();
        if (k == 0 || length == 0) { return 0; }
        k = min(k, length / 2);
        vector<vector<vector<int>>> dp(length, vector<vector<int>>(k + 1, {0, INT32_MIN}));
        dp[0][0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
            for (int j = 1; j <= k; j++) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);
            }
        }
        int res = 0;
        for (int i = 0; i <= k; i++) {
            res = max(res, dp[length - 1][i][0]);
        }
        return res;
    }
};

刷题总结

做股票类型的题目，一定要会动态规划，然后找出各个状态之间的变化，其实难度不大，小伙伴们可以将股票问题做归类，然后多练习两次，对动态规划的理解也会提高很多。