LeetCode 188. 买卖股票的最佳时机 IV 是股票系列问题的终极版本，要求在 最多进行 k 笔交易 的条件下，计算最大利润。

✅ 关键约束：
不能同时参与多笔交易（必须先卖出再买入）
一笔交易 = 一次买入 + 一次卖出

🧠 解题思路

核心思想：动态规划（DP） + 状态机

状态定义
我们定义两个 DP 数组：
buy[i][j]：第 i 天结束后，已完成 j 笔交易且当前持有股票 的最大利润
sell[i][j]：第 i 天结束后，已完成 j 笔交易且当前不持有股票 的最大利润

💡 注意：“完成 j 笔交易” 指已经卖出了 j 次

状态转移
买入（持有股票）：
要么前一天就持有：buy[i-1][j]
要么今天买入（前提是已完成 j 笔交易，所以用 sell[i-1][j]）：
buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i])

卖出（不持有股票）：
要么前一天就不持有：sell[i-1][j]
要么今天卖出（完成第 j 笔交易，所以用 buy[i-1][j-1]）：
sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i])

边界条件
第 0 天（i=0）：
buy[0][0] = -prices[0]（买入）
sell[0][0] = 0（不操作）
对于 j >= 1：buy[0][j] = sell[0][j] = -∞（不可能完成 ≥1 笔交易）

⚡ 重要优化：k 过大时退化为无限交易

在 n 天内，最多只能完成 n/2 笔交易（每天买卖一次）
如果 k >= n/2，问题退化为 LeetCode 122（无限次交易）
可用贪心法：O(n) 时间解决

✅ 这能避免 k 很大时 DP 超时（如 k=1e9, n=1000）

💻 Java 实现（空间优化版）

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

    int n = prices.length;
    
    // 优化：k 过大时退化为无限交易
    if (k >= n / 2) {
        return greedyMaxProfit(prices);
    }
    
    // buy[j]: 当前持有股票，已完成 j 笔交易的最大利润
    // sell[j]: 当前不持有股票，已完成 j 笔交易的最大利润
    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];
    
    // 初始化第 0 天
    buy[0] = -prices[0];
    sell[0] = 0;
    for (int j = 1; j  prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

}

🔍 算法详解

为什么需要 Integer.MIN_VALUE / 2？
防止 + prices[i] 时整数溢出
用足够小的负数表示“不可能状态”

为什么先更新 buy 再更新 sell？
sell[j] 依赖 buy[j-1]（前一天的状态）
如果先更新 sell，会使用当天已更新的 buy，导致错误

为什么返回 max(sell[0…k])？
最优解可能在少于 k 笔交易时达到（如股价一直下跌）

📊 示例验证

输入：
k = 2, prices = [3,2,6,5,0,3]

过程：
第 2 天买入（2），第 3 天卖出（6）→ 利润 4
第 5 天买入（0），第 6 天卖出（3）→ 利润 3
总利润 = 7

DP 状态变化（sell 数组）：
天数 sell[0] sell[1] sell[2]
0 0 -∞ -∞

1 0 0 -∞

2 0 4 -∞

3 0 4 4

4 0 4 4

5 0 7 7

✅ 最终结果 = max(0,7,7) = 7

⚙️ 复杂度分析
情况 时间复杂度 空间复杂度
k = n/2 O(n) O(1)

💡 实际中，k 通常较小，效率很高

✅ 总结
关键点 说明
状态设计 buy[j] 和 sell[j] 表示完成 j 笔交易的状态

转移方程 买入用 sell[j]，卖出用 buy[j-1]

k 优化 k >= n/2 时退化为贪心

边界处理 第 0 天初始化，防止溢出

💡 一句话口诀：
“k 大贪心，k 小 DP；持有看同层，卖出看前层”

此解法高效、鲁棒，是 LeetCode 官方推荐做法。