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

[chencl1986]

原题链接：123. 买卖股票的最佳时机 III

解题思路：

1. 截至第i天，当前已经交易过 2 次，每次交易都可以买（支出prices[i]）或卖（收入prices[i]），因此可以用长度为 4 的dp数组递推。

2. 每种交易，都要在之前交易的基础上进行，例如只有买入后，才可以卖出。因此 4 种状态转移方程为：

   • 0~i 天，只买入 1 次的最优状态，dp[0] = Math.max(dp[0], -prices[i]);，第一次交易没有前置状态。
   • 0~i 天，买入 1 次后，卖出的最优状态，dp[1] = Math.max(dp[1], dp[0] + prices[i]);。
   • 0~i 天，卖出 1 次后，在买入 1 次的最优状态，dp[2] = Math.max(dp[2], dp[1] - prices[i]);。
   • 0~i 天，买入 2 次，卖出 1 次后，在卖出 1 次的最优状态，dp[3] = Math.max(dp[3], dp[2] + prices[i]);。

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

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // 一共可以交易2次，每次有买卖两种状态，因此需要用2*2=4种状态递推
  // 偶数位置为买入，第一次买入需要支出prices[0]
  // 奇数位置为卖出，由于没有买入过股票，没法卖出，为0
  let dp = [-prices[0], 0, -prices[0], 0];

  // 递推每天的交易情况
  for (let i = 1; i < prices.length; i++) {
    // 递推第i天的4种交易状态
    dp[0] = Math.max(
      dp[0], // 0~i-1天的状态
      -prices[i], // 第i天的状态
    ); // 0~i天，只买入1次的最优状态，第一次交易没有前置状态
    dp[1] = Math.max(
      dp[1], // 0~i-1天的状态
      dp[0] + prices[i], // 第i天的状态
    ); // 0~i天，买入1次后，卖出的最优状态
    dp[2] = Math.max(
      dp[2], // 0~i-1天的状态
      dp[1] - prices[i], // 第i天的状态
    ); // 0~i天，卖出1次后，在买入1次的最优状态
    dp[3] = Math.max(
      dp[3], // 0~i-1天的状态
      dp[2] + prices[i], // 第i天的状态
    ); // 0~i天，买入2次，卖出1次后，在卖出1次的最优状态
  }

  // 卖出2次，一定会拿到最多利润
  return dp[3];
};