区间动态规划例题：带冷冻期的股票买卖问题（最多完成k笔交易） 题目描述 给定一个整数数组prices表示股票价格，以及整数k。你需要完成最多k笔交易（买入和卖出算一笔交易），但不能同时参与多笔交易（必须在再次购买前出售掉之前的股票），且卖出股票后有一天的冷冻期（冷冻期内不能买入股票）。求能获得的最大利润。 解题过程 第一步：问题分析 交易限制：最多完成k笔交易 状态转移：买入 → 卖出 → 冷冻期 → 买入 关键约束：卖出后需要等待一天才能再次买入 我们需要设计状态表示来记录这些限制条件 第二步：状态定义 定义三维DP数组： dp[i][j][0] ：第i天结束时，已经完成j笔交易，当前不持有股票的最大利润 dp[i][j][1] ：第i天结束时，已经完成j笔交易，当前持有股票的最大利润 由于冷冻期的存在，我们需要区分不同的不持有股票状态。 第三步：更精确的状态设计 重新设计为二维状态： dp[i][j] ：第i天结束时，处于状态j的最大利润 状态j的含义： j = 0：持有股票 j = 1：不持有股票，且不在冷冻期（可以买入） j = 2：不持有股票，且在冷冻期（刚卖出，不能买入） 第四步：状态转移方程 对于第i天（i ≥ 1）： 持有股票（状态0）： 可能是前一天就持有： dp[i-1][0] 可能是今天买入（前一天不在冷冻期）： dp[i-1][1] - prices[i] dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) 不持有股票，不在冷冻期（状态1）： 可能是前一天就不在冷冻期： dp[i-1][1] 可能是冷冻期结束： dp[i-1][2] dp[i][1] = max(dp[i-1][1], dp[i-1][2]) 不持有股票，在冷冻期（状态2）： 只能是今天卖出股票： dp[i-1][0] + prices[i] dp[i][2] = dp[i-1][0] + prices[i] 第五步：加入交易次数限制 我们需要增加一维来记录交易次数： dp[i][k][0] ：第i天，已完成k次交易，持有股票 dp[i][k][1] ：第i天，已完成k次交易，不持有且可买入 dp[i][k][2] ：第i天，已完成k次交易，不持有且在冷冻期 状态转移： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] - prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][2]) dp[i][k][2] = dp[i-1][k-1][0] + prices[i] （卖出完成一次交易） 第六步：边界条件初始化 dp[0][0][0] = -prices[0] （第0天买入） dp[0][0][1] = 0 （第0天不操作） dp[0][0][2] = -∞ （第0天不可能在冷冻期） 对于k > 0的情况，第0天不可能完成交易，初始为-∞ 第七步：最终答案 最大利润为所有可能情况的最大值： max(dp[n-1][k][1], dp[n-1][k][2]) ，其中k从0到最大交易次数 第八步：复杂度优化 由于状态只依赖于前一天，可以使用滚动数组将空间复杂度从O(n×k)优化到O(k)。 总结 这个问题通过巧妙的状态设计（区分不同的不持有状态）和交易次数记录，将复杂的约束条件转化为清晰的状态转移方程，是区间动态规划在状态机建模中的典型应用。