买卖股票的最佳时机 IV 图解题解

这道题到底在问什么

k,prices

2,[2,4,1]

输出

2

先想最直接的笨办法

DP 表跟着代码走：推进语句是：return sell[k]。处理过的部分不再重新枚举。（动画第 10 步）

最优解：一步一步想明白

1. 3下面 9 步动画会按主解代码推进，而不是泛泛讲题型。
2. 4先读清 买卖股票的最佳时机 IV 的输入输出DP 表跟着代码走：先把示例输入映射到代码参数：def maxProfit(self, k, prices):。
3. 5n = len(prices)；ans = 0DP 表跟着代码走：开局只立住必要变量：n = len(prices)；ans = 0。
4. 6for i in range(1, n):DP 表跟着代码走：主流程从这里开始：for i in range(1, n):。
5. 7if prices[i] > prices[i - 1]:DP 表跟着代码走：题目条件落到这一行：if prices[i] > prices[i - 1]:。
6. 8ans += prices[i] - prices[i - 1]DP 表跟着代码走：对应代码：ans += prices[i] - prices[i - 1]。这一行决定当前轮对答案有什么贡献。
7. 9k>=n//2 时转无限交易DP 表跟着代码走：边界跟着代码看：return ans。
8. 10return sell[k]DP 表跟着代码走：推进语句是：return sell[k]。处理过的部分不再重新枚举。
9. 11return sell[k]DP 表跟着代码走：到这里，k 已经能表达题目要求。
10. 12return：return sell[k]DP 表跟着代码走：最后检查返回形态：返回值、原地修改或设计类状态，要和 LeetCode 判题方式一致。
11. 15记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def maxProfit(self, k, prices):
        n = len(prices)
        if not prices or k == 0:
            return 0
        if k >= n // 2:
            ans = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    ans += prices[i] - prices[i - 1]
            return ans
        buy = [-10**18] * (k + 1)
        sell = [0] * (k + 1)
        for price in prices:
            for t in range(1, k + 1):
                buy[t] = max(buy[t], sell[t - 1] - price)
                sell[t] = max(sell[t], buy[t] + price)
        return sell[k]

复杂度

面试官可能追问