LeetCode：188.买卖股票的最佳时机 IV

题目：188.买卖股票的最佳时机 IV ↗

状态机建模#

在 2786.访问数组中的位置使分数最大中，只有奇/偶两种状态；而在这一题中，我们最多允许 $k$ 次交易，那么在任意一天，我们可能处于的状态有：

• 第 1 次持有（Buy 1）
• 第 1 次卖出（Sell 1）
• 第 2 次持有（Buy 2）
• 第 2 次卖出（Sell 2）
• …
• 第 $k$ 次持有（Buy $k$）
• 第 $k$ 次卖出（Sell $k$）

总共有 $2k$ 个状态。

状态转移方程#

设 $buy[j]$ 表示第 $j$ 次持有股票时的最大利润，$sell[j]$ 表示第 $j$ 次卖出股票后的最大利润。

对于当天的股价 $P$：

• 第 $j$ 次持有（$buy[i]$） 我可能今天继续持有昨天的股票，或者今天刚刚买入（前提是第 $j - 1$ 次交易已经卖出）： $buy[j] = \max(buy[j], sell[j-1] - P)$

• 第 $j$ 次卖 （$sell[j]$） 我可能今天继续空仓，或者今天刚刚卖出（前提是第 $j$ 次买入的股票还在手里）： $sell[j] = \max(sell[j], buy[j] + P)$

代码实现#

初始化：

• $buy$ 数组应该初始化最小值，因为都没开盘就持有股票，这是非法的，需要过滤掉
• $sell$ 数组应该初始化为 0，因为还没开始交易时利润为 0

public int maxProfit(int k, int[] prices) {
	if (prices.length == 0) return 0;

	// buy[j] 表示第 j + 1 次买入后的最大利润
	int[] buy = new int[k];
	// sell[j] 表示第 j + 1 次售出后的最大利润
	int[] sell = new int[k];

	Arrays.fill(buy, Integer.MIN_VALUE);

	for (int p : prices) {
		for (int j = 0; j < k; ++j) {
			int preSell = j == 0 ? 0 : sell[j - 1];
			buy[j] = Math.max(buy[j], preSell - p);
			sell[j] = Math.max(sell[j], buy[j] + p);
		}
	}

	return sell[k - 1];
}