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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：三维 DP（标准定义）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

定义状态 dp[j][0] 和 dp[j][1] 分别表示完成了 j 笔交易且当前不持有和持有股票时的最大利润（空间压缩后用一维数组）。

一笔完整交易包含一次买入和一次卖出，卖出时交易数 +1。

状态转移：

不持有：dp[j][0] = max(dp[j][0], dp[j][1] + prices[i])（继续不持有 / 今天卖出）

持有：dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i])（继续持有 / 今天买入，消耗上一笔交易的状态）

当 k >= n / 2 时，等价于可以无限次交易，退化为贪心：累加所有相邻正差值即可。

复杂度分析：

时间复杂度：O(n × k)，其中 n 表示价格数组长度，k 表示最多交易次数。

空间复杂度：O(k)，使用一维 DP 数组存储每笔交易的两个状态。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;

        // 当 k >= n/2 时，等价于无限次交易，使用贪心
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }

        // dp[j][0]：完成第 j 笔交易且不持有股票时的最大利润
        // dp[j][1]：完成第 j 笔交易且持有股票时的最大利润
        int[][] dp = new int[k + 1][2];
        for (int j = 0; j <= k; j++) {
            // 初始化：持有股票状态设为负无穷，表示尚未发生
            dp[j][1] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < n; i++) {
            // 逆序枚举，防止当天数据被重复使用
            for (int j = k; j >= 1; j--) {
                // 今天卖出，完成第 j 笔交易
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
                // 今天买入，开始第 j 笔交易（基于第 j-1 笔不持有状态）
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }

        // 返回最多 k 笔交易不持有股票时的最大利润
        return dp[k][0];
    }
}

func maxProfit(k int, prices []int) int {
    n := len(prices)

    // 当 k >= n/2 时，等价于无限次交易，使用贪心
    if k >= n/2 {
        profit := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                profit += prices[i] - prices[i-1]
            }
        }
        return profit
    }

    // dp[j][0]：完成第 j 笔交易且不持有股票时的最大利润
    // dp[j][1]：完成第 j 笔交易且持有股票时的最大利润
    dp := make([][2]int, k+1)
    for j := 0; j <= k; j++ {
        // 初始化：持有股票状态设为负无穷，表示尚未发生
        dp[j][1] = -1 << 31
    }

    for i := 0; i < n; i++ {
        // 逆序枚举，防止当天数据被重复使用
        for j := k; j >= 1; j-- {
            // 今天卖出，完成第 j 笔交易
            if val := dp[j][1] + prices[i]; val > dp[j][0] {
                dp[j][0] = val
            }
            // 今天买入，开始第 j 笔交易（基于第 j-1 笔不持有状态）
            if val := dp[j-1][0] - prices[i]; val > dp[j][1] {
                dp[j][1] = val
            }
        }
    }

    // 返回最多 k 笔交易不持有股票时的最大利润
    return dp[k][0]
}

解法二：三维 DP（标准定义）

核心思路：

定义 dp[i][j][s]：第 i 天、已完成 j 笔交易、持股状态为 s（0 不持有，1 持有）时的最大利润。

状态转移：

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])（继续持有 / 今天买入）

空间可进一步优化为滚动数组，此处展示原始三维定义便于理解。

复杂度分析：

时间复杂度：O(n × k)，其中 n 表示价格数组长度，k 表示最多交易次数。

空间复杂度：O(n × k)，三维 DP 表。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) {
            return 0;
        }

        // 当 k >= n/2 时，等价于无限次交易
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }

        // dp[i][j][s]：第 i 天完成 j 笔交易持股状态为 s 时的最大利润
        int[][][] dp = new int[n][k + 1][2];
        for (int j = 0; j <= k; j++) {
            // 第 0 天持有股票：花费 prices[0]
            dp[0][j][1] = -prices[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                // 不持有：继续不持有，或今天卖出
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                // 持有：继续持有，或今天买入（消耗第 j-1 笔交易的不持有状态）
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }

        return dp[n - 1][k][0];
    }
}

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 || k == 0 {
        return 0
    }

    // 当 k >= n/2 时，等价于无限次交易
    if k >= n/2 {
        profit := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                profit += prices[i] - prices[i-1]
            }
        }
        return profit
    }

    // dp[i][j][s]：第 i 天完成 j 笔交易持股状态为 s 时的最大利润
    dp := make([][][2]int, n)
    for i := range dp {
        dp[i] = make([][2]int, k+1)
    }

    // 第 0 天持有股票：花费 prices[0]
    for j := 0; j <= k; j++ {
        dp[0][j][1] = -prices[0]
    }

    for i := 1; i < n; i++ {
        for j := k; j >= 1; j-- {
            // 不持有：继续不持有，或今天卖出
            if val := dp[i-1][j][1] + prices[i]; val > dp[i-1][j][0] {
                dp[i][j][0] = val
            } else {
                dp[i][j][0] = dp[i-1][j][0]
            }
            // 持有：继续持有，或今天买入（消耗第 j-1 笔交易的不持有状态）
            if val := dp[i-1][j-1][0] - prices[i]; val > dp[i-1][j][1] {
                dp[i][j][1] = val
            } else {
                dp[i][j][1] = dp[i-1][j][1]
            }
        }
    }

    return dp[n-1][k][0]
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	贪心、动态规划
122. 买卖股票的最佳时机 II	中等	贪心、动态规划
123. 买卖股票的最佳时机 III	困难	动态规划、有限状态
309. 买卖股票的最佳时机含冷冻期	中等	动态规划、状态机
714. 买卖股票的最佳时机含手续费	中等	动态规划、贪心
1911. 最大子序列交替和	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/90547968