买卖股票的最佳时机 IV

🔴 Hard · 🏷️ 数组、动态规划 · LeetCode#188

📖 题目

给定 prices 数组和整数 k，最多完成 k 笔交易，求最大利润。

输入	输出
k=2, prices=[3,2,6,5,0,3]	7（第2天买第3天卖赚4，第5天买第6天卖赚3）

💡 思路

最多两次交易固定用了 buy1/sell1/buy2/sell2 四个状态，这题的 k 是变量，状态数也跟着变——泛化成两个长度为 k 的数组 buy[]、sell[]，转移逻辑跟123完全一样，只是从固定的4个变量变成了循环：

buy[0]  依赖 初始资金（0）
sell[0] 依赖 buy[0]
buy[j]  依赖 sell[j-1]   ← 用上一笔的利润去买
sell[j] 依赖 buy[j]

💻 代码

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        buy = [-prices[0]] * k
        sell = [0] * k
        for p in prices[1:]:
            buy[0] = max(buy[0], -p)
            sell[0] = max(sell[0], buy[0] + p)
            for i in range(1, k):
                buy[i] = max(buy[i], sell[i - 1] - p)
                sell[i] = max(sell[i], buy[i] + p)
        return sell[-1]

时间复杂度 O(n × k)，n 天乘 k 笔交易；空间复杂度 O(k)，两个长度为 k 的数组。buy[0] 单独处理是因为第一笔交易没有"上一笔利润"可以用，只能白手起家（max(buy[0], -p)）。

这是股票系列的终极形态——只交易一次、不限次数、最多两次都是这里 k=1、k=∞、k=2 的特殊情况。