LeetCode 题解工作台
买卖股票的最佳时机 V
给你一个整数数组 prices ，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k 。 你最多可以进行 k 笔交易，每笔交易可以是以下任一类型： 普通交易 ：在第 i 天买入，然后在之后的第 j 天卖出，其中 i 。你的利润是 prices[j] - prices[i] 。…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示在前 天内，最多进行 笔交易，且当前状态为 时的最大利润。这里的状态 有三种可能： - 若 $k = 0$，表示当前没有持有股票。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。
你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：
-
普通交易：在第
i天买入，然后在之后的第j天卖出，其中i < j。你的利润是prices[j] - prices[i]。 -
做空交易：在第
i天卖出，然后在之后的第j天买回，其中i < j。你的利润是prices[i] - prices[j]。
注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。
通过进行 最多 k 笔交易，返回你可以获得的最大总利润。
示例 1:
输入: prices = [1,7,9,8,2], k = 2
输出: 14
解释:
我们可以通过 2 笔交易获得 14 美元的利润：- 一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。
- 一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。
示例 2:
输入: prices = [12,16,19,19,8,1,19,13,9], k = 3
输出: 36
解释:
我们可以通过 3 笔交易获得 36 美元的利润：- 一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。
- 一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。
- 一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。
提示:
2 <= prices.length <= 1031 <= prices[i] <= 1091 <= k <= prices.length / 2
解题思路
方法一：动态规划
我们定义 表示在前 天内，最多进行 笔交易，且当前状态为 时的最大利润。这里的状态 有三种可能：
- 若 ，表示当前没有持有股票。
- 若 ，表示当前持有一支股票。
- 若 ，表示当前持有一支股票的空头。
初始时，对任意 ，都有 和 。这表示在第 0 天买入一支股票或卖出一支股票的空头。
接下来，我们可以通过状态转移来更新 的值。对于每一天 和每笔交易 ，我们可以根据当前状态 来决定如何更新：
- 若 ，表示当前没有持有股票，这个状态可以由以下三种情况转移而来：
- 前一天没有持有股票。
- 前一天持有一支股票，并在今天卖出。
- 前一天持有一支股票的空头，并在今天买回。
- 若 ，表示当前持有一支股票，这个状态可以由以下两种情况转移而来：
- 前一天持有一支股票。
- 前一天没有持有股票，并在今天买入。
- 若 ，表示当前持有一支股票的空头，这个状态可以由以下两种情况转移而来：
- 前一天持有一支股票的空头。
- 前一天没有持有股票，并在今天卖出。
即，对于 和 ，我们有以下状态转移方程：
最终，我们需要返回 ，即在前 天内，最多进行 笔交易，且当前没有持有股票时的最大利润。
时间复杂度 ，空间复杂度 。其中 为数组 的长度，而 为最大交易次数。
class Solution:
def maximumProfit(self, prices: List[int], k: int) -> int:
n = len(prices)
f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
for j in range(1, k + 1):
f[0][j][1] = -prices[0]
f[0][j][2] = prices[0]
for i in range(1, n):
for j in range(1, k + 1):
f[i][j][0] = max(
f[i - 1][j][0],
f[i - 1][j][1] + prices[i],
f[i - 1][j][2] - prices[i],
)
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
return f[n - 1][k][0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(k * n) using the DP table where n is the number of days and k is the transaction limit. Space complexity can be reduced from O(k * n) to O(k) by rolling arrays since each day depends only on the previous day states. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to define buy and sell states clearly in DP.
- question_mark
Look for awareness of edge cases where k exceeds half of prices length.
- question_mark
Check for correct indexing and transaction completion constraints.
常见陷阱
外企场景- error
Forgetting that you cannot buy and sell on the same day within overlapping transactions.
- error
Mishandling cases where k is larger than half the number of days.
- error
Using incorrect state transitions, leading to underestimated profits.
进阶变体
外企场景- arrow_right_alt
Unlimited transactions version reduces to simple peak-valley summation using O(n) scan.
- arrow_right_alt
Single transaction version simplifies to tracking minimum price and max profit in O(n).
- arrow_right_alt
Cooldown or transaction fee variations require modified DP states to include cooldown or cost.