LeetCode 3573. 买卖股票的最佳时机 V - 动态规划解法详解
题目描述
给你一个整数数组prices，其中prices[i]是第 i 天股票的价格，以及一个整数k。
你最多可以进行k 笔交易，每笔交易可以是以下任一类型：
- 普通交易（做多）：在第 i 天买入，然后在之后的第 j 天卖出（i < j）。利润 =
prices[j] - prices[i] - 做空交易：在第 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解题思路
问题分析
这道题的关键点在于：
- 支持两种交易类型：做多和做空
- 交易之间不能重叠（必须先结束一笔再开始下一笔）
- 需要找到最优的 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：初始空仓，收益为 0dp[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
初始化技巧：对所有 j 都初始化持有状态，避免复杂的边界判断
状态转移简洁：用嵌套
max函数，一行代码表达所有可能的转移
易错点
- ❌ 试图用绝对值统一处理做多和做空 → 无法正确追踪状态转移
- ❌ 交易数计数错位 → 应该在"平仓"时完成交易，而非"开仓"时
- ❌ 初始化不完整 → 导致某些状态无法转移
相关题目
- LeetCode 121. 买卖股票的最佳时机（k=1，只能做多）
- LeetCode 122. 买卖股票的最佳时机 II（k=∞）
- LeetCode 123. 买卖股票的最佳时机 III（k=2，只能做多）
- LeetCode 188. 买卖股票的最佳时机 IV（通用 k，只能做多）
本题是最通用的版本，同时支持做多和做空，难度更高。