[!info] related notes 动态规划 区间 DP 与状态机 DP 买卖股票的最佳时机

买卖股票的最佳时机 IV

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

状态设计

定义：

buy[t] = 至多完成 t - 1 次卖出并持有下一笔股票时的最大现金净额
sell[t] = 完成至多 t 次交易时，当前不持股的最大收益

其中一次完整交易是“买入 + 卖出”，同时最多持有一股。t 从 1 开始；buy[0] 不可达，sell[0] = 0。

转移

newBuy[t] = max(oldBuy[t], oldSell[t - 1] - price)
newSell[t] = max(oldSell[t], oldBuy[t] + price)

JavaScript

var maxProfit = function(k, prices) {
    if (prices.length === 0 || k === 0) return 0;

    const buy = new Array(k + 1).fill(-Infinity);
    const sell = new Array(k + 1).fill(0);

    for (const price of prices) {
        for (let t = k; t >= 1; t--) {
            sell[t] = Math.max(sell[t], buy[t] + price);
            buy[t] = Math.max(buy[t], sell[t - 1] - price);
        }
    }

    return sell[k];
};

代码按 t 逆序、先更新 sell 再更新 buy，确保读取上一天的状态。时间 O(nk)，空间 O(k)。