Skip to main content

最佳买卖股票时机含冷冻期

Tips

题目类型: Dynamic Programming

相关题目:

题目​

给定一个整数数组, 其中第 i 个元素代表了第 i 天的股票价格. 设计一个算法计算出最大利润. 在满足以下约束条件下, 你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票).
  • 卖出股票后, 你无法在第二天买入股票 (即冷冻期为 1 天).
示例

输入: [1,2,3,0,2]

输出: 3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题解​

这道题是在 122. 买卖股票的最佳时机-ii 的基础衍生的, 卖出股票后, 你无法在第二天买入股票, 也就是第 i 天选择买的时候, 要从 i - 2 状态转移, 而非 i - 1.

状态分析​

  • 状态一: 持有股票状态(今天买入股票, 或者是之前就买入了股票然后没有操作, 一直持有)

  • 不持有股票状态, 这里就有两种卖出股票状态

    • 状态二: 保持卖出股票的状态(两天前就卖出了股票, 度过一天冷冻期. 或者是前一天就是卖出股票状态, 一直没操作)
    • 状态三: 今天卖出股票

  • 状态四: 今天为冷冻期状态, 但冷冻期状态不可持续, 只有一天.

状态转移方程​

达到状态一:

  • 前一天就是买入了股票然后没有操作, 一直持有: dp[i][0] = dp[i - 1][0]
  • 今日买入股票:
    • 前一天是冷冻期: dp[i][0] = dp[i - 1][3]
    • 前一天是保持卖出股票的状态(也就是状态二): dp[i][0] = dp[i - 1][1] - prices[i]

达到状态二:

  • 两天前就卖出了股票, 前一天是冷冻期: dp[i][1] = dp[i - 1][3]
  • 前一天就是保持卖出股票的状态: dp[i][1] = dp[i - 1][1]

达到状态三:

  • 因为你必须在再次购买前出售掉之前的股票, 故卖出要从买入流转: dp[i][2] = dp[i - 1][0] + prices[i]

达到状态四:

  • 因为卖出股票后, 你无法在第二天买入股票, 故冷冻期的上一天一定是卖出操作: dp[i][3] = dp[i - 1][2]

状态转移方程​

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const n = prices.length
  const dp = new Array(n).fill(0).map(() => new Array(4).fill(0))

  dp[0][0] = -prices[0]
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][3], dp[i - 1][1] - prices[i])
    dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1])
    dp[i][2] = dp[i - 1][0] + prices[i]
    dp[i][3] = dp[i - 1][2]
  }

  return Math.max(dp[n - 1][3], dp[n - 1][2], dp[n - 1][1])
}