买卖股票的最佳时机-iii

Tips

题目类型: Dynamic Programming

题目

给定一个数组, 它的第 i 个元素是一支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润. 你最多可以完成两笔交易. 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票).

示例

输入: prices = [3,3,5,0,0,3,1,4]

输出: 6

解释: 在第 4 天(股票价格 = 0)的时候买入, 在第 6 天(股票价格 = 3)的时候卖出, 这笔交易所能获得利润 = 3-0 = 3. 随后, 在第 7 天(股票价格 = 1)的时候买入, 在第 8 天 (股票价格 = 4)的时候卖出, 这笔交易所能获得利润 = 4-1 = 3.

题解

状态分析

由于最多完成两笔交易, 意味着最终可能没有交易, 可能只有一次交易, 可能有两次交易.

对于某一天, 可能有五种状态:

无操作
第一次持有
第一次不持有
第二次持有
第二次不持有

因此: dp[i][j] 中 i 表示第 i 天, j 为五个状态的一种, dp[i][j] 表示第 i 天状态 j 所剩最大现金.

状态转移方程

达到 dp[i][1] 状态, 有两个具体操作:

第 i 天买入股票了, 那么 dp[i][1] = dp[i - 1][0] - prices[i]
第 i 天没有操作, 而是沿用前一天买入的状态, 即: dp[i][1] = dp[i - 1][1]

达到 dp[i][2] 状态, 有两个具体操作:

第 i 天卖出股票了, 那么 dp[i][2] = dp[i - 1][1] + prices[i]
第 i 天没有操作, 沿用前一天卖出股票的状态, 即: dp[i][2] = dp[i - 1][2]

达到 dp[i][3] 状态, 有两个具体操作:

第 i 天买入股票了, 那么 dp[i][3] = dp[i - 1][2] - prices[i]
第 i 天没有操作, 而是沿用前一天买入的状态, 即: dp[i][3] = dp[i - 1][3]

达到 dp[i][4] 状态, 有两个具体操作:

第 i 天卖出股票了, 那么 dp[i][4] = dp[i - 1][3] + prices[i]
第 i 天没有操作, 而是沿用前一天卖出的状态, 即: dp[i][4] = dp[i - 1][4]

初始化

在第 0 天, 如果第一次买入, 那 dp[0][1] = -prices[0]
在第 0 天, 如果第一次卖出, 那 dp[0][2] = 0, 你可以理解为先买入再卖出
在第 0 天, 如果第二次买入, 由于第二次买入需要建立在第一次买卖的基础上, 由于 dp[0][2] 是 0, 那 dp[0][3] = -prices[0].
在第 0 天, 如果第二次卖出, 那 dp[0][4] = 0, 你可以理解为第一次先买入再卖出, 第二次又先买入再卖出

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

  dp[0][1] = -prices[0]
  dp[0][3] = -prices[0]
  for (let i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0] // 从前一个无操作转移过来的
    dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])
    dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2])
    dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3])
    dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4])
  }

  return dp[n - 1][4]
}

时间复杂度: O(n)
空间复杂度: O(n * 5)

题目​

题解​

状态分析​

状态转移方程​

初始化​

题目

题解

状态分析

状态转移方程

初始化