一、什么是区间 DP
区间 DP 是在一个区间 [i, j] 上定义状态，通过枚举分割点 k 将大区间拆分为两个小区间来转移的 DP 模型。
核心特征：
- 状态：
dp[i][j]表示区间[i, j]的最优值 - 转移：枚举分割点
k，dp[i][j] = f(dp[i][k], dp[k+1][j]) - 遍历顺序：按区间长度从小到大
Mermaid · 渲染中（下方为源码）
graph TD A["dp[i][j]"] --> B["dp[i][k]"] A --> C["dp[k+1][j]"] B --> D["更小区间..."] C --> E["更小区间..."]
二、通用模板
// 初始化：长度为 1 的区间
for (int i = 0; i < n; i++) dp[i][i] = baseValue;
// 按长度从小到大枚举
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INF; // 或 0，取决于求 min 还是 max
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
}
}
}- 时间：O(n³)，空间：O(n²)
三、经典案例
3.1 戳气球（LeetCode 312）
问题：戳破气球 i 获得 nums[i-1] * nums[i] * nums[i+1] 硬币，求最大总硬币。
关键转化：不思考"先戳哪个"，而是思考"最后戳哪个"。
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1; // 虚拟边界
System.arraycopy(nums, 0, arr, 1, n);
int[][] dp = new int[n + 2][n + 2];
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
// k 是区间 [i,j] 中最后一个被戳的
int coins = arr[i - 1] * arr[k] * arr[j + 1];
dp[i][j] = Math.max(dp[i][j],
dp[i][k - 1] + coins + dp[k + 1][j]);
}
}
}
return dp[1][n];
}3.2 合并石子
问题：n 堆石子排成一行，每次合并相邻两堆（代价 = 两堆之和），求最小总代价。
public int mergeStones(int[] stones) {
int n = stones.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
dp[i][j] += prefix[j + 1] - prefix[i]; // 合并代价
}
}
return dp[0][n - 1];
}3.3 最长回文子序列
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}3.4 矩阵链乘法
问题：n 个矩阵相乘，不同的加括号方式导致不同的乘法次数，求最少次数。
public int matrixChainOrder(int[] p) {
int n = p.length - 1; // n 个矩阵
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}四、区间 DP 的识别信号
| 信号 | 示例 |
|---|---|
| "合并相邻元素" | 合并石子、戳气球 |
| "在区间上操作" | 回文子序列、矩阵链乘 |
| "分割成子区间" | 最优 BST、分割回文串 |
| 状态是 [i, j] 区间 | 任何 dp[i][j] 表示区间 |
五、优化方向
| 优化 | 条件 | 效果 |
|---|---|---|
| 四边形不等式 | cost 满足单调性 | O(n³) → O(n²) |
| 记忆化搜索 | 状态稀疏 | 减少无效计算 |
| 环形处理 | 首尾相连 | 数组翻倍（长度 2n） |
环形区间 DP
// 将数组复制一份，长度变为 2n
// 在 [0, 2n-1] 上做区间 DP
// 答案 = max/min(dp[i][i+n-1]) for i in [0, n-1]六、面试常见题
- 🟡 最长回文子序列、分割回文串 II
- 🟠 戳气球、合并石子、矩阵链乘法
- 🔴 移除盒子、奇怪的打印机、环形合并石子
七、调试技巧
- 遍历顺序：必须按长度从小到大，否则子问题未计算。
- 分割点范围：
k从i到j-1（不是j）。 - 边界初始化：
dp[i][i]是基础，别忘了。 - 区间越界：
i + len - 1 < n防止越界。