文章目录
区间动态规划 (Interval DP) 详解：从原理到实战（C++实现）
区间动态规划是动态规划中处理序列或区间最优解问题的一类重要方法。它通过定义状态来表示序列上的一段连续子区间，并推导状态之间的转移关系来解决复杂问题。本文将系统讲解区间DP的核心思想、常见模型、优化策略及C++实现。
一、区间DP基础概念
1.1 什么是区间DP
区间DP的核心状态定义为：
dp[i][j]：表示序列/区间 [i, j] 上的最优解（或某种状态）
通过枚举区间内的划分点 k，将大区间 [i, j] 拆分成两个子区间 [i, k] 和 [k+1, j]，利用子问题的最优解构造原问题的解：
dp[i][j] = min/max { dp[i][k] + dp[k+1][j] + cost(i, j, k) }
1.2 适用问题特征
- 序列结构：问题涉及线性序列（数组、字符串）
- 区间操作：操作或决策作用于连续子区间
- 最优子结构：大区间最优解依赖子区间最优解
- 重叠子问题：不同区间可能共享子问题
二、区间DP的通用解法框架
2.1 状态定义
// 通常使用二维dp数组
vector<vector<int>> dp(n, vector<int>(n, 0));
// dp[i][j] 表示区间[i, j]的答案
2.2 状态转移方程
for (int len = 2; len <= n; ++len) { // 枚举区间长度
for (int i = 0; i + len - 1 < n; ++i) { // 枚举起点
int j = i + len - 1; // 终点
dp[i][j] = INT_MAX; // 或INT_MIN
for (int k = i; k < j; ++k) { // 枚举分割点
dp[i][j] = min/max(dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, j, k));
}
}
}
2.3 初始化
- 单点区间：
dp[i][i] = base_value - 相邻区间：
dp[i][i+1] = cost(i, i+1)
三、经典例题详解（附C++代码）
3.1 石子合并（最小代价）
问题：N堆石子排成一线，每次合并相邻两堆，代价为两堆石子之和。求合并成一堆的最小总代价。
状态转移：
dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i, j) } for k in [i, j-1]
C++代码：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> stones(n);
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
cin >> stones[i];
prefix[i + 1] = prefix[i] + stones[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
// 初始化单点区间
for (int i = 0; i < n; ++i) dp[i][i] = 0;
// 枚举区间长度
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
int sum_ij = prefix[j + 1] - prefix[i]; // 区间和
for (int k = i; k < j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum_ij);
}
}
}
cout << dp[0][n - 1] << endl;
return 0;
}
3.2 最长回文子序列 (LPS)
问题：求给定字符串的最长回文子序列长度。
状态转移：
if (s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
C++代码：
#include <iostream>
#include <vector>
using namespace std;
int longestPalindromeSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 初始化：单个字符是长度为1的回文
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = (len == 2) ? 2 : dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
四、区间DP的四种常见模型
4.1 链式区间DP（石子合并类）
- 序列为线性链状结构
- 典型问题：矩阵链乘法、多边形三角剖分
4.2 环形区间DP
处理方法：破环成链（复制一倍数组）
vector<int> doubled(2 * n);
copy(original.begin(), original.end(), doubled.begin());
copy(original.begin(), original.end(), doubled.begin() + n);
4.3 记录决策点（输出具体方案）
增加 split[i][j] 数组记录最优分割点
if (newValue < dp[i][j]) {
dp[i][j] = newValue;
split[i][j] = k; // 记录最优分割位置
}
4.4 高维区间DP
三维DP处理更复杂结构（如二维矩阵）
dp[i][j][k] // 表示从i到j行，k列形成的区域
五、四边形不等式优化（Knuth优化）
5.1 适用条件
当代价函数 cost(i, j) 满足：
- 区间单调性：
cost(a, c) + cost(b, d) ≤ cost(b, c) + cost(a, d) (a≤b≤c≤d) - 四边形不等式：
dp[i][j] + dp[i+1][j+1] ≤ dp[i][j+1] + dp[i+1][j]
5.2 优化实现
使用 s[i][j] 记录最优分割点范围：
vector<vector<int>> s(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
dp[i][i] = 0;
s[i][i] = i; // 初始化最优分割点
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
int L = s[i][j-1], R = s[i+1][j]; // 缩小k的范围
dp[i][j] = INT_MAX;
for (int k = L; k <= R; ++k) {
int cost = dp[i][k] + dp[k+1][j] + prefix[j+1]-prefix[i];
if (cost < dp[i][j]) {
dp[i][j] = cost;
s[i][j] = k; // 更新最优分割点
}
}
}
}
时间复杂度：从 O(n³) 优化到 O(n²)
六、实战训练（附解法）
6.1 括号匹配（最大匹配数）
问题：求括号序列的最大匹配括号数
状态转移：
dp[i][j] = max(dp[i+1][j], dp[i][k-1] + dp[k+1][j] + 2)
// 当s[i]与s[k]匹配时
6.2 切木棍（最优切割成本）
问题：长度为L的木棍上有n个切割点，求最小总切割成本（每次切割成本=当前木棍长度）
解法：
- 添加虚拟切割点0和L
- 按坐标排序切割点数组
a[0..m+1] dp[i][j] = min{ dp[i][k] + dp[k][j] } + (a[j]-a[i])
七、区间DP技巧总结
- 破环成链：解决环形区间问题
- 前缀和优化：快速计算区间和
- 记忆化搜索：替代迭代DP（代码更简洁）
int dfs(int i, int j) {
if (dp[i][j] != -1) return dp[i][j];
if (i == j) return 0;
int res = INT_MAX;
for (int k = i; k < j; ++k)
res = min(res, dfs(i, k) + dfs(k+1, j) + sum(i, j));
return dp[i][j] = res;
}
- 状态压缩：当区间长度较小时用位运算
八、高频面试题精选
- 戳气球（LeetCode 312）
- 奇怪的打印机（LeetCode 664）
- 合并石头的最低成本（LeetCode 1000）
- 最长有效括号（LeetCode 32）
- 布尔括号化（计数问题）
九、区间DP扩展应用
9.1 树形区间DP
将区间DP思想扩展到树形结构：
dp[u][j] // 表示以u为根的子树中，选择j个节点的最优解
9.2 区间DP与线段树结合
- 动态维护区间信息
- 支持带修改的区间DP问题
9.3 概率区间DP
状态定义：dp[i][j] 表示区间[i,j]达成目标的概率
十、总结与学习建议
解题步骤：
- 识别区间特征
- 定义DP状态
- 推导转移方程
- 处理边界条件
- 优化时间复杂度
学习建议：
- 从经典问题（石子合并、LPS）入手
- 动手实现基础版本
- 逐步尝试优化技巧
- 多做变式训练（环形、高维）
重要提示：区间DP的代码实现中，务必注意循环顺序（长度->起点->分割点）和边界初始化！
附录：完整石子合并代码（四边形不等式优化版）
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
prefix[i + 1] = prefix[i] + arr[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
vector<vector<int>> s(n, vector<int>(n, 0)); // 最优决策点数组
// 初始化
for (int i = 0; i < n; ++i) {
s[i][i] = i;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
int L = s[i][j-1], R = (j < n-1) ? s[i+1][j] : j-1;
for (int k = L; k <= R; ++k) {
int cost = dp[i][k] + dp[k+1][j] + prefix[j+1] - prefix[i];
if (cost < dp[i][j]) {
dp[i][j] = cost;
s[i][j] = k;
}
}
}
}
cout << "Minimum merge cost: " << dp[0][n-1] << endl;
return 0;
}
通过系统学习区间DP的核心思想和解题技巧，你将能够高效解决各类区间最值问题。