学习笔记
跟着卡哥学算法Day 42：动态规划part9
正在加载今日诗词....
2025-03-25

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

力扣链接 🌟🌟🌟

题目描述

给定一个整数数组  prices ，它的第 i 个元素  prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  • 示例 1：
  • 输入：k = 2, prices = [2,4,1]
  • 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 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 。

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

解题思路

动态规划：123.买卖股票的最佳时机 III的进阶版，股票买卖可以 k 次交易

延续之前的思路，每天有多种状态：

  1. dp[i][0] 表示第 i 天没有任何操作
  2. dp[i][1] 表示第 i 天第一次买入股票
  3. dp[i][2] 表示第 i 天第一次卖出股票
  4. dp[i][3] 表示第 i 天第二次买入股票
  5. dp[i][4] 表示第 i 天第二次卖出股票
  6. ......
  • 除了 0 以外，偶数就是卖出，奇数就是买入
  • 最多 k 笔交易，j 的最大值为 2k+1，即 k=3 需要计算到 dp[i][6]，以此类推

动规五部曲：

  1. 确定 dp 数组及下标的含义

    dp[i][j] 中 i 表示第 i 天，j 表示多种状态[0-2k+1]，所以 dp[i][j]表示第 i 天状态 j 下所剩最大金额

  2. 确定递推公式

    想要达到 dp[i][1]，有两种情况：

    1. 第 i 天买入股票，即 dp[i][1] = dp[i-1][0] - prices[i]
    2. 第 i 天没操作，即 dp[i][1] = dp[i-1][1]

    取两者最大值：

    dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])

    想要达到 dp[i][2]，有两种状态：

    1. 第 i 天卖出股票，即 dp[i][2] = dp[i-1][1] + prices[i]
    2. 第 i 天没操作，即 dp[i][2] = dp[i-1][2]

    取两者最大值：

    dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i])

    以此类推：

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

  3. dp 数组初始化

    • dp[0][0] = 0，第 0 天不做操作，金额为 0
    • dp[0][1] = -prices[0]，第 0 天买入股票，所得最金额为 -prices[0]
    • dp[0][2] = 0，第 0 天卖出股票，所得最金额为 0
    • 以此类推，
    // 奇数为买入，价格为 -prices[0]
// 偶数卖出，都是0
for (let j = 1; j < 2 * k + 1; j += 2) {
  dp[0][j] = -prices[0]
}

  4. 确定遍历顺序

    从前往后

  5. 举例推导 dp 数组

    以 prices = [1,2,3,4,5]，k=2 为例，得到的 dp 数组为：

    dp = [
  [0, -1, 0, -1, 0],
  [0, -1, 1, -1, 1],
  [0, -1, 2, -1, 2],
  [0, -1, 3, -1, 3],
  [0, -1, 4, -1, 4],
]

代码

var maxProfit = function (k, prices) {
  const n = prices.length
  const max = 2 * k + 1
  const dp = new Array(n).fill().map(() => new Array(max).fill(0))

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

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

  return dp[n - 1][max - 1]
}

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

力扣链接 🌟🌟

题目描述

给定一个整数数组，其中第  i  个元素代表了第  i  天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

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

示例:

  • 输入: [1,2,3,0,2]
  • 输出: 3
  • 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

在动态规划：122.买卖股票的最佳时机 II的基础上，增加了冷冻期的概念

之前共有两种状态：

  1. 第 i 天持有股票（今天买入，或之前就买入后没有操作）
  2. 第 i 天不持有股票（今天卖出，或之前卖出后没有操作）

那么，此题加了冷冻期的概念，状态可以有以下四种情况：

  1. 第 i 天持有股票（和上面一样）
  2. 第 i 天不持有股票
    1. 第 i 天保持卖出股票状态（i-2 天卖出股票，度过一天冷冻期；或者 i-2 就是卖出状态，没有操作）
    2. 第 i 天卖出股票，与之前买卖股票的不同点
  3. 第 i 天为冷冻期，冷冻期状态不可持续，只有一天

与之前买卖股票的不同点：第 i 天卖出股票单独列为一个状态，为什么？

此题包含冷冻期，需要清楚的知道前一天是否卖出股票，才能知道当天是否为冷冻期

动规五部曲：

  1. 确定 dp 数组及下标的含义

    • dp[i][0] 表示第 i 天持有股票所得最多现金
    • dp[i][1] 表示第 i 天不持有股票所得最多现金
    • dp[i][2] 表示第 i 天卖出股票所得最多现金
    • dp[i][3] 表示第 i 天为冷冻期所得最多现金

  2. 确定递推公式

    dp[i][0] 即第 i 天持有股票的最大金额，可以由两个状态推出：

    1. dp[i - 1][0] 即第 i-1 天持有股票的最大金额
    2. dp[i - 1][3] - prices[i] 即第 i - 1 天为冷冻期，今日买入
    3. dp[i - 1][1] - prices[i] 即第 i- 1 天为保持卖出股票状态，今日买入

    dp[i][0] 在两者中选最大的：

    dp[i][0] = Math.max(
  dp[i - 1][0],
  dp[i - 1][1] - prices[i],
  dp[i - 1][3] - prices[i]
)

    dp[i][1] 即第 i 天不持有股票的最大金额，可以由两个状态推出：

    1. dp[i - 1][1] 即第 i-1 天不持有股票的最大金额
    2. dp[i - 1][3] 即第 i-1 天为冷冻期

    取两者最大值：

    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])

    dp[i][2] 即第 i 天卖出股票的最大金额，只能由一个状态推出，i-1 天必须时持有股票状态：

    dp[i][2] = dp[i - 1][0] + prices[i]

    dp[i][3] 即第 i 天为冷冻期，冷冻期状态不可持续，只有一天，只能由一个状态推出，i-1 天必须卖出股票：

    dp[i][3] = dp[1 - 1][2]

    因此，递推公式为：

    dp[i][0] = Math.max(
  dp[i - 1][0],
  dp[i - 1][1] - prices[i],
  dp[i - 1][3] - prices[i]
)
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])
dp[i][2] = dp[i - 1][0] + prices[i]
dp[i][3] = dp[i - 1][2]

  3. dp 数组初始化

    • dp[0][0] = -prices[0]，第 0 天持有股票，即买入，所得现金为 -prices[0]
    • dp[0][1] = 0，第 0 天不持有股票
    • dp[0][2] = 0，第 0 天卖出股票

  4. 确定遍历顺序

    从前往后

  5. 举例推导 dp 数组

    以 prices = [1,2,3,0,2] 为例，得到的 dp 数组为：

    dp = [
  [-1, 0, 0, 0],
  [-1, 0, 1, 0],
  [-1, 0, 2, 1],
  [1, 1, -1, 2],
  [1, 2, 3, -1],
]

    最后取 dp[i][1]、dp[i][2] 和 dp[i][3] 中的最大值，即为最大利润

代码

var maxProfit = function (prices) {
  const n = prices.length
  const dp = new Array(n).fill().map(() => [0, 0, 0, 0])

  dp[0][0] = -prices[0]

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

  console.log(dp)

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

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

力扣链接 🌟🌟

题目描述

定一个整数数组  prices，其中第  i  个元素代表了第  i  天的股票价格 ；非负整数  fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

  • 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
  • 输出: 8

解释: 能够达到的最大利润:

  • 在此处买入  prices[0] = 1
  • 在此处卖出 prices[3] = 8
  • 在此处买入 prices[4] = 4
  • 在此处卖出 prices[5] = 9
  • 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

解题思路

在动态规划：122.买卖股票的最佳时机 II的基础上，增加了手续费

那么，只需要在卖出的时候减去手续费就可以

动规五部曲：

  1. 确定 dp 数组及下标的含义

    • dp[i][0] 表示第 i 天持有股票的状态
    • dp[i][1] 表示第 i 天不持有股票的状态

  2. 确定递归公式

    达到 dp[i][0] 状态有两种情况：

    1. 第 i 天买入股票，那么 dp[i][0] = dp[i-1][1] - prices[i]
    2. 第 i 天保持现状，沿用前一天买入股票的状态，即：dp[i][0] = dp[i-1][0]

    两者选择最大的：

    dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0])

    同理，达到 dp[i][1] 状态有两种情况：

    1. 第 i 天卖出股票，那么 dp[i][1] = dp[1 - 1][0] + prices[i] - fee，需要减去手续费
    2. 第 i 天保持现状，沿用前一天卖出股票的状态，即：dp[i][1] = dp[i-1][1]
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)

  3. dp 数组初始化

    • dp[0][0] = -prices[i]，第 0 天买入股票，所得现金为 -prices[0]
    • dp[0][1] = 0，第 0 天第一次买入股票，金额为 -prices[0]

  4. 确定遍历顺序

    从前往后

  5. 举例推导 dp 数组

    以 prices = [1, 3, 2, 8, 4, 9], fee = 2 为例，得到的 dp 数组为：

    dp = [
  [
    [-1, 0],
    [-1, 0],
    [-1, 0],
    [-1, 5],
    [1, 5],
    [1, 8],
  ],
]

代码

var maxProfit = function (prices, fee) {
  const n = prices.length
  const dp = new Array(n).fill().map(() => [0, 0])

  // 0持有
  // 1不持有
  dp[0][0] = -prices[0]

  for (let i = 1; i < n; i++) {
    const price = prices[i]
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - price)
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + price - fee)
  }
  console.log(dp)

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

买卖股票问题总结

动态规划通用思路

股票问题的动态规划解法，状态由以下两个核心维度定义：

  1. 天数（i 表示第 i 天）。
  2. 持有状态（0 表示不持有股票，1 表示持有股票）。
  3. 附加维度（交易次数 k、冷冻期、手续费等，根据题目添加）。

状态转移方程

1. 基础模板（无附加约束）

  • 状态定义：

    dp[i][k][0/1]：第 i 天，最多完成 k 次交易，当前是否持有股票时的最大利润。
    （实际应用中可简化维度，如 k 固定或通过滚动数组优化空间）

  • 转移方程：

    • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
      （不持有股票：前一天不持有，或当天卖出）
    • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
      （持有股票：前一天持有，或当天买入，需消耗一次交易机会）

2. 不同题型的变体

题目附加约束状态转移调整要点
121. 买卖一次k=1简化状态：dp[i][0/1]，买入时只能从初始状态转移
122. 买卖多次k= +∞移除 k 维度：dp[i][0/1]，买入时直接继承前一天的利润
123. 买卖两次k=2显式定义 k 维度，遍历 k 从 1 到 2
188. 买卖 K 次k 任意通用化 k 维度，注意 k 上限优化（当 k > n/2 时退化为无限次交易）
309. 含冷冻期卖出后等待一天引入冷冻期状态：卖出后跳过一天才能买入
714. 含手续费每次交易扣手续费在买入或卖出时扣除手续费（通常统一在卖出时扣除）

五、通用解题步骤

  1. 定义状态：根据题目约束，明确状态维度（持有状态、交易次数、冷冻期等）。
  2. 推导转移方程：基于题目规则，分情况讨论状态转移。
  3. 初始化边界：设置第 0 天的初始值（如 dp[0][1] = -prices[0]）。
  4. 处理特殊约束：如冷冻期需延迟状态更新，手续费在交易时扣除。

京ICP备2022027737号
Copyright © 2022 - present @wangxiang

  • ☀️
  • 🌑