LeetCode 题解工作台
买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。 注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 …
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j, k)$，表示从第 天开始，最多完成 笔交易，以及当前持有股票的状态为 （不持有股票用 表示，持有股票用 表示）时，所能获得的最大利润。答案即为 $dfs(0, k, 0)$。 函数 $dfs(i, j, k)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 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 。
提示：
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从第 天开始，最多完成 笔交易，以及当前持有股票的状态为 （不持有股票用 表示，持有股票用 表示）时，所能获得的最大利润。答案即为 。
函数 的执行逻辑如下：
- 如果 大于等于 ，直接返回 ；
- 第 天可以不进行任何操作，那么 ；
- 如果 ，那么第 天可以选择卖出股票，那么 ；
- 否则，如果 ，那么第 天可以选择买入股票，那么 。
取上述三种情况的最大值即为 的值。
过程中，我们可以使用记忆化搜索的方法，将每次计算的结果保存下来，避免重复计算。
时间复杂度 ，空间复杂度 。其中 和 分别为数组 的长度和 的值。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j, k)
if k:
ans = max(ans, prices[i] + dfs(i + 1, j, 0))
elif j:
ans = max(ans, -prices[i] + dfs(i + 1, j - 1, 1))
return ans
return dfs(0, k, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*k) for standard DP updates or O(n) if k >= n/2 using unlimited transaction optimization. Space complexity is O(k) for compressed DP arrays holding only the last day states. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect clear DP state definition and correct transitions between hold and cash arrays.
- question_mark
Clarify handling of edge cases where k is very large relative to the number of days.
- question_mark
Explain why multiple simultaneous transactions are invalid and how DP enforces this.
常见陷阱
外企场景- error
Attempting to buy and sell on the same day without proper DP transitions.
- error
Not optimizing for cases where k is large, leading to unnecessary computation.
- error
Incorrect initialization of hold and cash arrays causing off-by-one or negative profits.
进阶变体
外企场景- arrow_right_alt
Unlimited transactions version where k is effectively infinite, simplifying DP updates.
- arrow_right_alt
Single transaction (k=1) version reduces to simple max profit calculation.
- arrow_right_alt
Transaction fee variant where each sell reduces profit, requiring adjusted state transitions.