Best Time to Buy and Sell Stock IV

188. 买卖股票的最佳时机IV

分析

无交易限制的情况：
- 当 k >= n / 2（即可以无限次交易的情况），那么我们可以通过每次只要当前价格比前一天高就进行交易，获取利润
- 这种情况下，我们只需要遍历数组，当 prices[i] < prices[i + 1] 时，进行买卖，利润就会累加
有交易次数限制的情况：
- 当 k < n / 2 时，我们需要考虑最多进行 k 次交易的情况。为此，我们需要使用动态规划来计算不同交易次数的最大利润
- 使用动态规划状态 f[i][j] 表示前 i 天内进行 j 次交易的最大利润。我们还可以使用辅助数组 g[i][j] 来记录前 i 天内进行 j-1 次交易，买入股票时的状态（即股票买入价格的最优状态）
- 每次更新 f[i][j] 和 g[i][j] 时，考虑的是：
  - 卖出：通过 g[i-1][j] + prices[i-1] 来记录前 i-1 天完成 j 次交易的最大利润加上当前价格（即卖出）
  - 买入：通过 f[i-1][j-1] - prices[i-1] 来记录前 i-1 天完成 j-1 次交易的最大利润减去当前价格（即买入）
状态转移方程
- f[i][j] = max(f[i-1][j], g[i-1][j] + prices[i-1])：卖出时，选择前 i-1 天进行 j 次交易的最大利润，再加上今天卖出的利润
- g[i][j] = max(g[i-1][j], f[i-1][j-1] - prices[i-1])：买入时，选择前 i-1 天进行 j-1 次交易的最大利润，再减去今天买入的价格

时间复杂度

时间复杂度 O(k * n)

空间复杂度

空间复杂度为 O(k * n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class Solution
{
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int res = 0;
        int n = prices.size();

        // 交易次数 k 大于等于 n / 2，则可以进行无限次交易
        if (k >= n / 2)
        {
            for (int i = 0; i < n - 1; ++i)
                if (prices[i] < prices[i + 1])
                    res += prices[i + 1] - prices[i];  // 贪心：只要后一天价格高于前一天就交易
            return res;
        }

        int INF = 0x3f3f3f3f;
        vector<vector<int>> f(n + 1, vector<int>(k + 1, -INF));  // 动态规划数组，初始化为一个大负值
        vector<vector<int>> g = f;  // 辅助数组，用于存储买入操作时的状态

        f[0][0] = 0;  // 在第 0 天，不进行任何交易，利润为 0

        // 遍历每一天
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= k; ++j)
            {
                // 若不做交易，利润保持不变。若交易，进行卖出操作
                f[i][j] = max(f[i - 1][j], g[i - 1][j] + prices[i - 1]);

                g[i][j] = g[i - 1][j];  // 不进行买入操作

                if (j)  // 如果可以进行交易
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] - prices[i - 1]);  // 进行买入操作

                res = max(res, f[i][j]);  // 更新最大利润
            }

        return res;  // 返回最终的最大利润
    }
};