LeetCode 题解工作台
买卖股票的最佳时机含冷冻期
给定一个整数数组 prices ，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意： 你不能同时参与多笔交易（你必须在再…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j)$，表示从第 天开始，状态为 时，能够获得的最大利润。其中 的取值为 $0, 1$，分别表示当前不持有股票和持有股票。答案即为 $dfs(0, 0)$。 函数 $dfs(i, j)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从第 天开始，状态为 时，能够获得的最大利润。其中 的取值为 ，分别表示当前不持有股票和持有股票。答案即为 。
函数 的执行逻辑如下：
如果 ，表示已经没有股票可以交易了，此时返回 ；
否则，我们可以选择不交易，此时 。我们也可以进行股票交易，如果此时 ，说明当前持有股票，可以卖出，此时 ；如果此时 ，说明当前不持有股票，可以买入，此时 。取最大值作为函数 的返回值。
答案为 。
为了避免重复计算，我们使用记忆化搜索的方法，用一个数组 记录 的返回值，如果 不为 ，说明已经计算过，直接返回 即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j)
if j:
ans = max(ans, prices[i] + dfs(i + 2, 0))
else:
ans = max(ans, -prices[i] + dfs(i + 1, 1))
return ans
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate correctly identifies the need for dynamic programming.
- question_mark
Candidate uses a space-optimized solution.
- question_mark
Candidate understands state transition and cooldown mechanics.
常见陷阱
外企场景- error
Forgetting to handle the cooldown after selling the stock.
- error
Incorrectly calculating profit by not tracking the maximum at each state transition.
- error
Using O(n) space when O(1) space is possible.
进阶变体
外企场景- arrow_right_alt
Modifying the problem to include transaction limits.
- arrow_right_alt
Allowing only one transaction (single buy and sell).
- arrow_right_alt
Adding more complicated cooldown conditions, such as cooldown lengths longer than one day.