动态规划困难1 种解法
#188买卖股票的最佳时机 IV
最多完成 k 笔交易且同一时间只能持有一股，求最大利润。
#数组#动态规划#状态机#股票
原题
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
解题主线
- 用已完成的卖出次数刻画交易次数：cash[t] 表示恰好完成 t 笔后不持股，hold[t] 表示恰好完成 t 笔后仍持股。
- 买入不会增加已完成交易数，卖出会使次数从 t - 1 增加到 t。
- 一笔完整交易至少需要买入和卖出两个时点，有效交易上限可截断为 min(k, n / 2)。
解法 1：按完成交易数动态规划
严格区分恰好完成 t 笔交易的持股与不持股状态，每天从上一天的数组生成新状态，最后在至多 k 个不持股状态中取最大值。
-
时间复杂度： O(n × min(k, n / 2))
-
空间复杂度： O(min(k, n / 2))
import java.util.Arrays;
final class Solution {
private static final int UNREACHABLE = Integer.MIN_VALUE;
public int maxProfit(int k, int[] prices) {
if (k <= 0 || prices == null || prices.length < 2) {
return 0;
}
// 有效交易数不会超过 n / 2，截断可避免维护永远不可达的状态。
int transactions = Math.min(k, prices.length / 2);
int[] cash = new int[transactions + 1];
int[] hold = new int[transactions + 1];
// cash[t]/hold[t] 表示恰好完成 t 笔交易后的不持股/持股状态。
Arrays.fill(cash, UNREACHABLE);
Arrays.fill(hold, UNREACHABLE);
cash[0] = 0;
hold[0] = -prices[0];
for (int day = 1; day < prices.length; day++) {
int price = prices[day];
// 从前一天快照转移，禁止同一天更新出的状态再次参与计算。
int[] nextCash = cash.clone();
int[] nextHold = hold.clone();
for (int completed = 0; completed <= transactions; completed++) {
if (cash[completed] != UNREACHABLE) {
nextHold[completed] = Math.max(
nextHold[completed], cash[completed] - price
);
}
// 卖出才完成一笔交易，因此从 hold[completed - 1] 转入。
if (completed > 0 && hold[completed - 1] != UNREACHABLE) {
nextCash[completed] = Math.max(
nextCash[completed], hold[completed - 1] + price
);
}
}
cash = nextCash;
hold = nextHold;
}
// 题目限制“至多”k 笔，答案应覆盖所有可达的完成次数。
int answer = 0;
for (int completed = 0; completed <= transactions; completed++) {
answer = Math.max(answer, cash[completed]);
}
return answer;
}
}实现提示
- 从上一天克隆再转移，避免原地更新把同一天的新状态误当成前一天状态。
边界与易错点
- 旧源码把每个交易次数的首日持股状态都初始化为 -prices[0]，与“恰好完成 t 笔”的注释不一致；整理后用不可达哨兵严格初始化。
- 不可达状态不能默认填 0，否则会凭空获得已经完成多笔交易的现金。
- 答案要取所有 cash[t] 的最大值，因为题目要求至多 k 笔，而不是必须完成 k 笔。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/greedy/Q188_maxStockProfit_IV.java