买卖股票最佳时机 IV

[!abstract] 问题 最多交易 k 次，不能同时持有多股。

示例

输入: k = 2, prices = [2,4,1]
输出: 2
解释: 第2天买入(4)，第3天卖出(1)，利润=2

解法

DP

function maxProfit(k: number, prices: number[]): number {
  const n = prices.length;
  if (n === 0 || k === 0) return 0;

  // 偶数位(0,2,4...): 卖出状态
  // 奇数位(1,3,5...): 买入状态
  const dp = Array(n).fill(0).map(() => Array(2 * k + 1).fill(0));

  // 初始化所有买入状态
  for (let j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < 2 * k; j += 2) {
      // 买入
      dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
      // 卖出
      dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
    }
  }

  return dp[n-1][2 * k];
}

空间优化

function maxProfitOptimized(k: number, prices: number[]): number {
  const n = prices.length;
  if (n === 0 || k === 0) return 0;

  // 只需要保留当前和上一个状态
  const dp = Array(2 * k + 1).fill(0);

  for (let j = 1; j < 2 * k; j += 2) {
    dp[j] = -prices[0];
  }

  for (let i = 1; i < n; i++) {
    for (let j = 2 * k - 1; j >= 0; j--) {
      if (j % 2 === 0) {
        // 卖出状态
        dp[j] = Math.max(dp[j], dp[j-1] + prices[i]);
      } else {
        // 买入状态
        dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
      }
    }
  }

  return dp[2 * k];
}

通用状态机

k 次交易 → 2k 个状态
状态 0:    初始（未开始）
状态 1:    第一次买入后
状态 2:    第一次卖出后
状态 3:    第二次买入后
...
状态 2k:   第 k 次卖出后

复杂度

维度	复杂度
时间	O(n × k)
空间	O(k)

---

参见: **股票问题** | **买卖股票最佳时机III**