买卖股票的最佳时机-iv

Tips

题目类型: Dynamic Programming

题目

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

示例

输入: k = 2, prices = [2,4,1]
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入,
      在第 2 天 (股票价格 = 4) 的时候卖出, 这笔交易所能获得利润为 4 - 2 = 2.

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

题解

状态分析

这道题其实跟第 123. 买卖股票的最佳时机-iii 一样, 只不过那道题最多交易 2 次, 这道题不确定. 但我们可以借鉴它的逻辑:

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

因此共有 2 * k + 1 种状态, dp[i][j] 中 i 表示第 i 天, j 为 2 * k + 1 个状态的一种, dp[i][j] 表示第 i 天状态 j 所剩最大现金.

状态转移方程

我们根据第 123. 买卖股票的最佳时机-iii 的规律能得出:

当 j 为奇数时, 为持有状态
当 j 为偶数时, 为不持有状态、

因此:

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

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

达到 dp[i][j + 2], 即不持有状态: 有两个具体操作:

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

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

  for (let j = 1; j < 2 * k + 1; j += 2) {
    dp[0][j] = -prices[0]
  }

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

  return dp[n - 1][2 * k]
}

题目​

题解​

状态分析​

状态转移方程​

题目

题解

状态分析

状态转移方程