My Muri Life

切换主题

本页目录

股票买卖篇 ​

通用情况 ​

参考文章 中文版、英文版

  • 状态定义：
    • dp[i][k][0] = x，在第i天结束时，最多进行k次交易的情况下不持有股票可以获得的最大收益为x；
    • dp[i][k][1] = y，在第i天结束时，最多进行k次交易的情况下持有股票可以获得的最大收益为y。
  • base case：
    • dp[-1][k][0] = 0，第一天对应i = 0，i = -1表示没有进行任何股票交易，故值为0；
    • dp[-1][k][1] = -Infinity，没有进行任何交易的情况下不可能持游股票，我们需要求最大收益，故值为-Infinity；
    • dp[i][0][0] = 0，由于k = 0表示不允许进行任何股票交易，故值为0；
    • dp[i][0][1] = -Infinity，不允许进行任何股票交易的情况下也不可能持游股票，我们需要求最大收益，故值为-Infinity。
  • 状态转移方程：
    • dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    • dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])。

买卖股票的最佳时机 ​

121. 买卖股票的最佳时机

由于交易次数k = 1，对状态转移已经没有影响了，所以此时有：

  • 状态定义：dp[i][0] = x, dp[i][0] = y；
  • base case：
    • dp[0][0] = Math.max(dp[-1][0], dp[-1][1] + prices[0]) = Math.max(0, -Infinity + prices[0]) = 0；
    • dp[0][1] = Math.max(dp[-1][1], dp[-1][0] - prices[0]) = Math.max(-Infinity, 0 - prices[0]) = -prices[0]；
  • 状态转移方程：
    • dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])；
    • dp[i][1] = Math.max(dp[i-1][1], -prices[i])，此处由于dp[i-1][0][0] = 0，故dp[i-1][0][0] - prices[i]可简写为-prices[i]。
JavaScript
const maxProfit = prices => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => [0, 0])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], - prices[i])
  }
  return dp[len - 1][0]
}

时间复杂度：O(n)；空间复杂度：O(n)。

买卖股票的最佳时机 II ​

122. 买卖股票的最佳时机 II

由于交易次数k = Infinity，则k和k - 1可以看成是相同的，所以此时有：

  • 状态定义：dp[i][0] = x, dp[i][0] = y；
  • base case：
    • dp[0][0] = 0；
    • dp[0][1] = -prices[0]；
  • 状态转移方程：
    • dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])；
    • dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])，此处由于k = k-1（k = Infinity），可将dp[i-1][k-1][0] - prices[i]转化为dp[i-1][k][0] - prices[i]。
JavaScript
const maxProfit = prices => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => [0, 0])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  }
  return dp[len - 1][0]
}

时间复杂度：O(n)；空间复杂度：O(n)。

买卖股票的最佳时机 III ​

123. 买卖股票的最佳时机 III

由于交易次数k = 2，所以此时有：

  • 状态定义：dp[i][k][0] = x, dp[i][k][0] = y；
  • base case：
    • dp[0][2][0] = dp[0][1][0] = 0；
    • dp[0][2][1] = dp[0][1][1] = -prices[0]；
  • 状态转移方程：
    • dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])；
    • dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])。
JavaScript
const maxProfit = prices => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => Array(3).fill(0).map(_ => [0, 0]))
  dp[0][2][0] = dp[0][1][0] = 0
  dp[0][2][1] = dp[0][1][1] = -prices[0]
  for (let i = 1; i < len; i++) {
    dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
    dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
    dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
    dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][1] - prices[i])
  }
  return dp[len - 1][2][0]
}

时间复杂度：O(n)；空间复杂度：O(n)。

买卖股票的最佳时机 IV ​

188. 买卖股票的最佳时机 IV

有分析可知，设len = prices.length当交易次数k >= (len >> 1)时，最大收益就不再取决于允许的最大交易次数k，而是取决于股票价格数组的长度len：

  • 状态定义：dp[i][k][0] = x, dp[i][k][0] = y；
  • base case：
    • dp[0][i][0] = 0；
    • dp[0][i][1] = -prices[0]；
  • 状态转移方程：
    • dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])；
    • dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])。
JavaScript
const kInfinity = prices => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => [0, 0])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  }
  return dp[len - 1][0]
}
const maxProfit = (k, prices) => {
  const len = prices.length
  if (k >= (len >> 1)) {
    return kInfinity(prices)
  }
  const dp = Array(len).fill(0).map(_ => Array(k + 1).fill(0).map(_ => [0, 0]))
  for (let i = 1; i <= k; i++) {
    dp[0][i][0] = 0
    dp[0][i][1] = -prices[0]
  }
  for (let i = 1; i < len; i++) {
    for (let j = k; j > 0; j--) {
      dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
      dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
    }
  }
  return dp[len - 1][k][0]
}

时间复杂度：O(nk)；空间复杂度：O(nk)。

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

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

此题与买卖股票的最佳时机 II非常相似，只是增加了冷冻期的限制，因此需要对状态转移方程进行一些修改，所以此时有：

  • 状态定义：dp[i][0] = x, dp[i][0] = y；
  • base case：
    • dp[0][0] = 0；
    • dp[0][1] = -prices[0]；
  • 状态转移方程：
    • dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])；
    • dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i])。
JavaScript
const maxProfit = prices => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => [0, 0])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], (i >= 2 ? dp[i - 2][0] : 0) - prices[i])
  }
  return dp[len - 1][0]
}

时间复杂度：O(n)；空间复杂度：O(n)。

买卖股票的最佳时机含手续费 ​

309. 买卖股票的最佳时机含手续费

此题与买卖股票的最佳时机 II非常相似，只是增加了手续费的限制，因此需要对状态转移方程进行一些修改，所以此时有：

  • 状态定义：dp[i][0] = x, dp[i][0] = y；
  • base case：
    • dp[0][0] = 0；
    • dp[0][1] = -prices[0] - fee；
  • 状态转移方程：
    • dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])；
    • dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]) - fee。
JavaScript
const maxProfit = (prices, fee) => {
  const len = prices.length
  const dp = Array(len).fill(0).map(_ => [0, 0])
  dp[0][0] = 0
  dp[0][1] = -prices[0] - fee
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
  }
  return dp[len - 1][0]
}

时间复杂度：O(n)；空间复杂度：O(n)。