区间与状态机 DP
动态规划 ⭐⭐⭐ 进阶 🔥 高频
💡 核心要点
- 区间 DP：答案与连续区间相关，大区间由小区间合并/分割得到；遍历顺序必须从短区间到长区间
- 状态机 DP：每个时刻处于某个"状态"，先画状态转移图，图画好了方程自然就写出来了
- 两类问题都有固定的建模套路，掌握框架后可以快速识别并套用
Part 1：区间 DP
识别信号
遇到以下特征，优先考虑区间 DP：
- 问题的答案与一段连续区间
[l, r]相关 - 大区间的最优解可以通过枚举某个分割点，由若干小区间的最优解合并或分割得到
- 典型描述：合并石子、戳气球、括号合法性、矩阵链乘法、多边形剖分
通用思考框架
第一步：定义状态
dp[l][r] = 区间 [l, r] 上问题的最优解（最大值/最小值/方案数等）l 和 r 分别是区间的左右端点（通常下标从 1 开始，方便处理边界）。
第二步：状态转移——枚举分割点 k
区间 DP 的核心操作是枚举分割点 k，将 [l, r] 拆分为 [l, k] 和 [k+1, r] 两个子区间：
dp[l][r] = max/min over k in [l, r-1] of { dp[l][k] + dp[k+1][r] + cost(l, k, r) }有时候更自然的思路是**"最后一次操作"思维**：想象对区间 [l, r] 执行一系列操作，最后一次操作涉及哪个元素/位置？
为什么"最后操作"思维有效？
假设最后操作作用在 k 上：
- 在执行最后一步之前，
k把区间分成了[l, k-1]和[k+1, r]两部分 - 这两部分的操作已经相互独立地完成了
- 因此子问题
dp[l][k-1]和dp[k+1][r]不会相互干扰，可以分别求最优
这是区间 DP 有别于线性 DP 的关键：线性 DP 从左到右逐步扩展，而区间 DP 从内向外层层包裹。
第三步：遍历顺序——区间长度从小到大
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点
int r = l + len - 1; // 确定右端点
for (int k = l; k < r; k++) { // 枚举分割点
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
}
}
}为什么必须从短区间到长区间？
dp[l][r] 的值依赖于 dp[l][k] 和 dp[k+1][r]，而这两个子区间的长度都严格小于 r - l + 1。因此，当我们计算长度为 len 的区间时，所有长度小于 len 的区间必须已经计算完毕。
如果按行或按列遍历，会出现计算 dp[l][r] 时子区间还没被填好的情况，导致错误结果。
第四步：初始化
长度为 1 的区间（单个元素）是边界条件，通常直接赋值：
for (int i = 1; i <= n; i++) {
dp[i][i] = base_value; // 根据题意，可能是 0、元素值等
}第五步：时间与空间复杂度
- 时间复杂度：O(n³)——三层循环（区间长度 × 左端点 × 分割点）
- 空间复杂度：O(n²)——二维 dp 数组
典型例题：戳气球
题目描述：有 n 个气球，编号 0 到 n-1，每个气球上有数字 nums[i]。戳破气球 i 可以得到 nums[i-1] * nums[i] * nums[i+1] 枚硬币（边界外视为 1）。求戳破所有气球能获得的最多硬币数。
五步法分析
第一步：找到"最后操作"的关键洞察
直觉上我们想枚举"第一个戳哪个气球"，但这行不通——戳破气球 i 后，i-1 和 i+1 会变成相邻，子问题边界会动态变化，子问题之间不独立。
正确做法：枚举哪个气球最后被戳破。
为什么这样有效？如果气球 k 是区间 [l, r] 中最后一个被戳破的，那么在戳 k 之前，[l, k-1] 和 [k+1, r] 的气球都已经戳完了。此时 k 的邻居正好是 nums[l-1]（左边界外）和 nums[r+1]（右边界外），不再变动。子问题因此独立。
第二步：添加虚拟气球
在两端各添加一个值为 1 的虚拟气球，避免边界讨论：
int[] balloons = new int[n + 2];
balloons[0] = balloons[n + 1] = 1;
for (int i = 1; i <= n; i++) balloons[i] = nums[i - 1];第三步：状态定义
dp[l][r] = 戳破开区间 (l, r) 内所有气球能获得的最大硬币数注意这里用开区间，l 和 r 是不会被戳的边界气球（虚拟或真实）。这样转移时 balloons[l] 和 balloons[r] 始终是固定的边界。
第四步：状态转移
枚举开区间 (l, r) 中最后一个被戳破的气球 k：
dp[l][r] = max over k in (l, r) of {
dp[l][k] + balloons[l] * balloons[k] * balloons[r] + dp[k][r]
}解释：
dp[l][k]：先将(l, k)内的气球全部戳完balloons[l] * balloons[k] * balloons[r]：最后戳 k，此时左邻是 l，右邻是 rdp[k][r]：再将(k, r)内的气球全部戳完
第五步：遍历顺序与初始化
- 初始化：
dp[i][i+1] = 0（开区间内没有气球，硬币为 0），已由数组初始化覆盖 - 遍历：区间长度从 2 到 n+1（开区间长度），从小到大
Java 实现：
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
// 添加虚拟气球
int[] b = new int[n + 2];
b[0] = b[n + 1] = 1;
for (int i = 1; i <= n; i++) b[i] = nums[i - 1];
// dp[l][r] = 开区间 (l, r) 内所有气球戳完的最大硬币
int[][] dp = new int[n + 2][n + 2];
// 枚举开区间长度（至少为 2，即内部有气球）
for (int len = 2; len <= n + 1; len++) {
for (int l = 0; l + len <= n + 1; l++) {
int r = l + len;
// 枚举最后一个被戳破的气球 k
for (int k = l + 1; k < r; k++) {
int coins = b[l] * b[k] * b[r] + dp[l][k] + dp[k][r];
dp[l][r] = Math.max(dp[l][r], coins);
}
}
}
return dp[0][n + 1];
}
}复杂度分析：
- 时间：O(n³)——三层枚举
- 空间：O(n²)——dp 数组
延伸题目
| 题目 | 链接 | 与典型题的区别 | 关键技巧 |
|---|---|---|---|
| 石子合并 | 经典题（POJ 1995 等） | 合并型：将相邻堆合并为一堆，求最小/最大代价 | 分割点枚举，合并代价 = 两堆总数量（用前缀和 O(1) 查询） |
| 多边形三角剖分最低得分 | LC 1039 | 三角形划分：固定一条边，枚举第三个顶点 k | 环形结构→固定顶点 0，枚举区间 [l, r] 和三角形顶点 k，dp[l][r] = min(dp[l][k] + dp[k][r] + val[l]*val[k]*val[r]) |
Part 2：状态机 DP
识别信号
遇到以下特征，优先考虑状态机 DP：
- 问题涉及一系列决策（如买卖、持有、冷却等），每个时刻处于某个有限状态之一
- 不同状态之间有明确的转移规则（哪些状态可以互相切换，切换的条件和代价）
- 典型描述：股票买卖系列、任务调度、游戏状态切换
通用思考框架
第一步：先画状态转移图
这是状态机 DP 最核心的一步，图画好了，方程自然就写出来了。
- 节点 = 所有可能的状态
- 有向边 = 合法的状态转移
- 边上的标签 = 转移的代价（收益为正，损失为负）
示例（通用股票状态机）：
buy(-price) sell(+price)
not_holding ──────────→ holding ──────────→ not_holding
↑ │
└───────────────────── rest ───────────────────┘画图的过程迫使你枚举所有状态和所有合法转移，不会遗漏。
第二步：状态定义
dp[i][s] = 处理到第 i 天，处于状态 s 时，能获得的最大/最小收益s 是状态编号，通常用常量或枚举表示，使代码可读。
第三步：建模技巧——将约束转化为状态或转移代价
| 约束类型 | 建模方法 |
|---|---|
| 冷冻期（卖出后 k 天不能买） | 增加"冷冻"状态，冷冻期结束后才能转移到"可买"状态 |
| 交易次数限制（最多 k 次） | 增加交易次数维度：dp[i][j][s]，j 表示已完成 j 次交易 |
| 每次交易有手续费 | 在"卖出"转移的代价上减去 fee |
| 必须先买后卖 | 由"持有"状态的存在自然保证，不需要额外约束 |
第四步：股票系列统一框架
所有股票问题都是以下通用状态机的特殊情形：
核心状态：
holding：当前持有股票not_holding：当前不持有股票，且可以买入frozen（可选）：刚卖出，处于冷冻期，不能立即买入
核心转移：
not_holding[i] = max(
not_holding[i-1], // rest：继续不持有
frozen[i-1] // 冷冻期结束，恢复可买（可选）
)
holding[i] = max(
holding[i-1], // rest：继续持有
not_holding[i-1] - price[i] // buy：花钱买入
)
frozen[i] = holding[i-1] + price[i] // sell：卖出，进入冷冻（可选）
not_holding[i] = max(
not_holding[i-1],
holding[i-1] + price[i] // sell（无冷冻时）
)通过调整这个框架的参数，即可覆盖所有股票变体。
典型例题：买卖股票含冷冻期
题目描述：每天可以买入或卖出一支股票，卖出后第二天进入冷冻期，不能买入。求最大利润。
五步法分析
第一步：画状态转移图
三个状态：
0：not_holding——不持股，且可以买入1：holding——持有股票2：frozen——冷冻期（刚卖出，今天不能买）
buy(-price)
0 ─────────────→ 1
↑ │
│ sell(+price) │
│ ←──────────────
2 ←──────────────
sell(+price)
0 → 0 (rest)
1 → 1 (rest)
2 → 0 (冷冻期结束)文字描述转移关系：
not_holding→holding：买入，花费price[i]holding→frozen：卖出，获得price[i]frozen→not_holding：冷冻结束，无代价not_holding→not_holding：休息holding→holding：休息
第二步：状态定义
dp[i][0] = 第 i 天结束后，处于 not_holding 状态的最大利润
dp[i][1] = 第 i 天结束后，处于 holding 状态的最大利润
dp[i][2] = 第 i 天结束后，处于 frozen 状态的最大利润第三步：状态转移方程
根据状态图直接写出：
dp[i][0] = max(dp[i-1][0], dp[i-1][2]) // 继续不持有 或 冷冻期结束
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) // 继续持有 或 今天买入
dp[i][2] = dp[i-1][1] + prices[i] // 今天卖出，进入冷冻第四步：初始化
dp[0][0] = 0 // 第 0 天不持有，利润为 0
dp[0][1] = -prices[0] // 第 0 天买入，利润为负
dp[0][2] = Integer.MIN_VALUE / 2 // 第 0 天不可能处于冷冻状态第五步：答案
最终答案是 max(dp[n-1][0], dp[n-1][2])（不持有股票的两种状态取最大）。
Java 实现：
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
// dp[i][0]: not_holding, dp[i][1]: holding, dp[i][2]: frozen
int[][] dp = new int[n][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = Integer.MIN_VALUE / 2; // 不可达状态
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]); // rest 或 冷冻解除
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // rest 或 买入
dp[i][2] = dp[i-1][1] + prices[i]; // 卖出
}
return Math.max(dp[n-1][0], dp[n-1][2]);
}
}空间优化到 O(1)：
注意 dp[i] 只依赖 dp[i-1]，可以用滚动变量替代数组：
class Solution {
public int maxProfit(int[] prices) {
int notHold = 0;
int hold = -prices[0];
int frozen = Integer.MIN_VALUE / 2;
for (int i = 1; i < prices.length; i++) {
int newNotHold = Math.max(notHold, frozen);
int newHold = Math.max(hold, notHold - prices[i]);
int newFrozen = hold + prices[i];
notHold = newNotHold;
hold = newHold;
frozen = newFrozen;
}
return Math.max(notHold, frozen);
}
}注意：必须用临时变量保存旧值，不能原地更新，否则会用到本轮已更新的状态。
复杂度分析：
- 时间：O(n)
- 空间：O(1)（优化后）
延伸题目
| 题目 | 链接 | 与典型题的区别 | 关键技巧 |
|---|---|---|---|
| 买卖股票 I | LC 121 | 只能交易一次 | 状态机退化为两状态；也可简化为维护前缀最小值 O(n) |
| 买卖股票 II | LC 122 | 无限次交易，无冷冻 | 两状态（持有/不持有），无冷冻无次数限制 |
| 买卖股票 III | LC 123 | 最多 2 次交易 | 增加交易次数维度：dp[i][k][s]，k ∈ |
| 买卖股票 IV | LC 188 | 最多 k 次交易 | III 的泛化；当 k ≥ n/2 时退化为无限次（按 II 处理，防止 TLE） |
| 含手续费 | LC 714 | 每次卖出有手续费 | 在"卖出"转移时减去 fee 即可：notHold = max(notHold, hold + price - fee) |
常见陷阱与调试
💡 高频错误总结
区间 DP：
遍历顺序错误：按行/列遍历而非按区间长度遍历，导致依赖的子区间尚未计算。
- 调试方法：打印 dp 数组，检查小区间是否先于大区间被填充。
分割点范围越界：
k的范围是[l, r-1]（闭区间分割）或(l, r)（开区间分割），混淆会导致空区间计算。- 记住：分割点必须使两个子区间都非空。
忽略添加虚拟边界：戳气球类题目不加边界气球，转移时越界访问。
- 凡是涉及"相邻元素乘积"的区间 DP，考虑在两端补虚拟元素。
前缀和未预处理：石子合并类题目每次计算区间和是 O(n)，导致总复杂度变成 O(n⁴)。
- 提前计算前缀和，让区间和查询降至 O(1)。
状态机 DP：
不可达状态初始化为 0：例如第 0 天冷冻状态不可能出现，应初始化为极小值（
Integer.MIN_VALUE / 2），否则会产生非法转移路径。- 用
MIN_VALUE / 2而非MIN_VALUE，防止加法时整数溢出。
- 用
空间优化时原地更新：用滚动变量优化空间时，直接覆盖旧值导致同一轮循环内后续状态用到了已更新的值。
- 始终用临时变量保存本轮所有旧值，更新完毕后再赋值。
买卖次数定义模糊："一次交易"是指一次买+一次卖，不要把"买"和"卖"分别计数。
忘记处理 k ≥ n/2 的退化情形（LC 188）：k 很大时按通用框架会超时，应特判为无限次交易。