LeetCode题解：188. 买卖股票的最佳时机 IV，动态规划，JavaScript，详细注释

[chencl1986]

原题链接：188. 买卖股票的最佳时机 IV

解题思路：

该题与123. 买卖股票的最佳时机 III类似，只是交易次数有2次改为了k次。如果没有思路可以先看123题的题解。

1. 截至第i天，当前已经交易过 2 次，每次交易都可以买（支出prices[i]）或卖（收入prices[i]），因此可以用长度为 k * 2 的dp数组递推。
2. 每种交易，都要在之前交易的基础上进行，例如只有买入后，才可以卖出。因此状态转移方程为：

// j为遍历dp的索引
// 0~i天，交易k次的状态，每次买入或卖出，都在上一次交易的基础上进行
dp[j] = Math.max(
    dp[j], // 0~i-1天的状态
    dp[j - 1] + (j & 1 ? price : -price), // 第i天的状态
);

3. 卖出k次获得的利润一定是最多的，因此最大利润就在dp[dp.length - 1]。

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (k, prices) {
  // 一共可以交易2次，每次有买卖两种状态，因此需要用k*2种状态递推
  let dp = new Array(k * 2);

  // 偶数位置为买入，第一次买入需要支出prices[0]
  // 奇数位置为卖出，由于没有买入过股票，没法卖出，为0
  for (let i = 0; i < dp.length; i++) {
    dp[i] = i & 1 ? 0 : -prices[0];
  }

  // 从i=1天开始，递推每天的交易情况
  for (let i = 1; i < prices.length; i++) {
    const price = prices[i]; // 缓存当天的价格

    // 0~i天，只买入1次的最优状态，第一次交易没有前置状态
    dp[0] = Math.max(dp[0], -price);

    // 0~i天，交易k次的状态，每次买入或卖出，都在上一次交易的基础上进行
    for (let j = 1; j < dp.length; j++) {
      dp[j] = Math.max(
        dp[j], // 0~i-1天的状态
        dp[j - 1] + (j & 1 ? price : -price), // 第i天的状态
      );
    }
  }

  // 卖出次数最多时，利润也最大。
  // k为0时，利润为0
  return dp[dp.length - 1] || 0;
};