LeetCode 3573. 买卖股票的最佳时机 V - 动态规划解法详解

题目描述

给你一个整数数组prices，其中prices[i]是第 i 天股票的价格，以及一个整数k。

你最多可以进行k 笔交易，每笔交易可以是以下任一类型：

1. 普通交易（做多）：在第 i 天买入，然后在之后的第 j 天卖出（i < j）。利润 =prices[j] - prices[i]
2. 做空交易：在第 i 天卖出，然后在之后的第 j 天买回（i < j）。利润 =prices[i] - prices[j]

限制条件：

• 必须在开始下一笔交易前完成当前交易
• 不能在同一天进行多次买入或卖出操作

返回可以获得的最大总利润。

示例

示例 1:

输入: prices = [1,7,9,8,2], k = 2 输出: 14 解释: - 普通交易：第 0 天买入(1)，第 2 天卖出(9)，利润 = 8 - 做空交易：第 3 天卖出(8)，第 4 天买回(2)，利润 = 6 - 总利润 = 8 + 6 = 14

示例 2:

输入: prices = [12,16,19,19,8,1,19,13,9], k = 3 输出: 36 解释: - 普通交易：买入(12)，卖出(19)，利润 = 7 - 做空交易：卖出(19)，买回(8)，利润 = 11 - 普通交易：买入(1)，卖出(19)，利润 = 18 - 总利润 = 7 + 11 + 18 = 36

解题思路

问题分析

这道题的关键点在于：

1. 支持两种交易类型：做多和做空
2. 交易之间不能重叠（必须先结束一笔再开始下一笔）
3. 需要找到最优的 k 笔交易组合

状态定义

使用三维 DP 数组：dp[i][j][s]

• i：当前是第 i 天（0 ≤ i < n）
• j：已完成的交易数（0 ≤ j ≤ k）
• s：当前状态
  • s = 0：空仓（不持有任何头寸）
  • s = 1：做多持有（已买入，等待卖出）
  • s = 2：做空持有（已卖出，等待买回）

dp[i][j][s]表示：第 i 天、完成 j 笔交易、处于状态 s 时的最大收益。

状态转移方程

1. 空仓状态dp[i][j][0]

可以从以下状态转移而来：

• 保持空仓：dp[i-1][j][0]
• 做多平仓（卖出）：dp[i-1][j][1] + prices[i]（完成第 j 笔交易）
• 做空平仓（买回）：dp[i-1][j][2] - prices[i]（完成第 j 笔交易）

dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i], dp[i-1][j][2] - prices[i])

注意：平仓操作会完成一笔交易，所以从j状态平仓。

2. 做多持有状态dp[i][j][1]

可以从以下状态转移而来：

• 继续持有：dp[i-1][j][1]
• 今天买入：dp[i-1][j-1][0] - prices[i]（开始新交易）

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

注意：开始新交易时，从j-1的空仓状态转移（因为这笔交易还未完成）。

3. 做空持有状态dp[i][j][2]

可以从以下状态转移而来：

• 继续持有：dp[i-1][j][2]
• 今天卖空：dp[i-1][j-1][0] + prices[i]（开始新交易）

dp[i][j][2] = max(dp[i-1][j][2], dp[i-1][j-1][0] + prices[i])

初始化

第 0 天的状态：

• dp[0][0][0] = 0：初始空仓，收益为 0
• dp[0][j][1] = -prices[0]：第 0 天买入，成本为负
• dp[0][j][2] = prices[0]：第 0 天卖空，收益为正

对于所有j ∈ [1, k]，都初始化持有状态，这样可以简化边界处理。

最终答案

dp[n-1][k][0]：最后一天、完成 k 笔交易、空仓状态的最大收益。

代码实现

funcmaximumProfit(prices[]int,kint)int64{n:=len(prices)dp:=make([][][]int64,n)fori:=rangedp{dp[i]=make([][]int64,k+1)forj:=rangedp[i]{dp[i][j]=make([]int64,3)}}// 初始化第 0 天的状态forj:=1;j<=k;j++{dp[0][j][1]=int64(-prices[0])dp[0][j][2]=int64(prices[0])}fori:=1;i<n;i++{forj:=1;j<=k;j++{dp[i][j][0]=max(dp[i-1][j][0],max(dp[i-1][j][1]+int64(prices[i]),dp[i-1][j][2]-int64(prices[i])))dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-int64(prices[i]))dp[i][j][2]=max(dp[i-1][j][2],dp[i-1][j-1][0]+int64(prices[i]))}}returndp[n-1][k][0]}funcmax(a,bint64)int64{ifa>b{returna}returnb}

复杂度分析

• 时间复杂度：O(n × k)

  • 需要遍历 n 天，每天处理 k 个交易数状态
  • 每个状态的转移是 O(1)

• 空间复杂度：O(n × k)

  • DP 数组大小为 n × (k+1) × 3

空间优化

可以使用滚动数组优化，只保留前一天的状态，将空间复杂度降到 O(k)：

funcmaximumProfit(prices[]int,kint)int64{n:=len(prices)prev:=make([][]int64,k+1)curr:=make([][]int64,k+1)forj:=0;j<=k;j++{prev[j]=make([]int64,3)curr[j]=make([]int64,3)}forj:=1;j<=k;j++{prev[j][1]=int64(-prices[0])prev[j][2]=int64(prices[0])}fori:=1;i<n;i++{forj:=1;j<=k;j++{curr[j][0]=max(prev[j][0],max(prev[j][1]+int64(prices[i]),prev[j][2]-int64(prices[i])))curr[j][1]=max(prev[j][1],prev[j-1][0]-int64(prices[i]))curr[j][2]=max(prev[j][2],prev[j-1][0]+int64(prices[i]))}prev,curr=curr,prev}returnprev[k][0]}

关键要点总结

1. 区分做多和做空：必须用两个不同的状态来表示，因为它们的收益计算方式不同

   • 做多：买入（负收益）→ 卖出（正收益）
   • 做空：卖出（正收益）→ 买回（负收益）

2. 交易完成时机：从持有状态转到空仓状态时，才算完成一笔交易，交易数 +1

3. 初始化技巧：对所有 j 都初始化持有状态，避免复杂的边界判断

4. 状态转移简洁：用嵌套max函数，一行代码表达所有可能的转移

易错点

1. ❌ 试图用绝对值统一处理做多和做空 → 无法正确追踪状态转移
2. ❌ 交易数计数错位 → 应该在"平仓"时完成交易，而非"开仓"时
3. ❌ 初始化不完整 → 导致某些状态无法转移

相关题目

• LeetCode 121. 买卖股票的最佳时机（k=1，只能做多）
• LeetCode 122. 买卖股票的最佳时机 II（k=∞）
• LeetCode 123. 买卖股票的最佳时机 III（k=2，只能做多）
• LeetCode 188. 买卖股票的最佳时机 IV（通用 k，只能做多）

本题是最通用的版本，同时支持做多和做空，难度更高。