动态规划困难1 种解法

#188买卖股票的最佳时机 IV

最多完成 k 笔交易且同一时间只能持有一股，求最大利润。

#数组#动态规划#状态机#股票

解题主线

用已完成的卖出次数刻画交易次数：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))

188. 买卖股票的最佳时机 IV · 按完成交易数动态规划

java

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;
        }

        int transactions = Math.min(k, prices.length / 2);
        int[] cash = new int[transactions + 1];
        int[] hold = new int[transactions + 1];
        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
                    );
                }
                if (completed > 0 && hold[completed - 1] != UNREACHABLE) {
                    nextCash[completed] = Math.max(
                        nextCash[completed], hold[completed - 1] + price
                    );
                }
            }
            cash = nextCash;
            hold = nextHold;
        }

        int answer = 0;
        for (int completed = 0; completed <= transactions; completed++) {
            answer = Math.max(answer, cash[completed]);
        }
        return answer;
    }
}

严格区分恰好完成 t 笔交易的持股与不持股状态，每天从上一天的数组生成新状态，最后在至多 k 个不持股状态中取最大值。

从上一天克隆再转移，避免原地更新把同一天的新状态误当成前一天状态。

边界与易错点

旧源码把每个交易次数的首日持股状态都初始化为 -prices[0]，与“恰好完成 t 笔”的注释不一致；整理后用不可达哨兵严格初始化。
不可达状态不能默认填 0，否则会凭空获得已经完成多笔交易的现金。
答案要取所有 cash[t] 的最大值，因为题目要求至多 k 笔，而不是必须完成 k 笔。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q188_maxStockProfit_IV.java