买卖股票的最佳时机 IV

状态机 DP 进阶题：限制最多 k 次交易，需要在状态里加入交易次数维度。

#resource / algorithm #type / snippet #status / growing #source / leetcode #algo / dp

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

买卖股票的最佳时机 IV

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

状态设计

定义：

buy[t] = 完成至多 t 次交易时，当前持股的最大收益
sell[t] = 完成至多 t 次交易时，当前不持股的最大收益

其中一次完整交易是“买入 + 卖出”。

转移

buy[t] = max(buy[t], sell[t - 1] - price)
sell[t] = max(sell[t], buy[t] + price)

JavaScript

var maxProfit = function(k, prices) {
    if (prices.length === 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 = 1; t <= k; t++) {
            buy[t] = Math.max(buy[t], sell[t - 1] - price);
            sell[t] = Math.max(sell[t], buy[t] + price);
        }
    }

    return sell[k];
};