动态规划系统课程 · 第四讲：区间 DP¶
学习目标： 掌握
dp[l][r]这种二维状态，理解“区间 DP 为什么按照长度递增计算”，并通过 石子合并、最长回文子序列、矩阵链乘法 三道经典题建立完整的区间 DP 思维。
一、什么是区间 DP？¶
前面学习的 DP：
线性 DP¶
通常是：
dp[i]
表示处理到第 i 个位置时的最优答案。
背包 DP¶
通常是：
dp[j]
表示容量为 j 时的最优答案。
而区间 DP 的核心状态通常是：
dp[l][r]
表示：
区间
[l,r]内的某个问题的最优解。
例如：
1 2 3 4 5 6 7
└─────┘
[3,7]
dp[3][7] 就表示区间 [3,7] 的答案。
二、为什么区间 DP 会出现？¶
区间 DP 通常出现在这样的题目中：
给定一段序列，每次对其中一部分进行操作，要求最终整个区间的最优结果。
典型特征：
- 对一个连续区间进行操作。
- 大区间可以拆成若干小区间。
- 小区间的答案可以帮助计算大区间。
- 经常出现“最后一次合并”“最后一次切割”“最后一次操作”。
因此遇到：
区间 + 合并/分割/消除 + 最优
就应该警惕：
区间 DP¶
三、区间 DP 最重要的状态¶
最常见：
$$
dp[l][r]
$$
表示：
区间
[l,r]的最优答案。
但是仅仅写出这个还不够。
真正困难的是：
如何把
[l,r]拆成更小的区间？
最经典的方法是：
[l, r]
↓
[l, k] + [k+1, r]
也就是枚举一个分割点 k。
四、区间 DP 的核心转移结构¶
假设：
dp[l][r]
可以由：
dp[l][k]
和：
dp[k+1][r]
组合得到。
那么：
$$
dp[l][r]
=
\operatorname{opt}
\left(
dp[l][k]+dp[k+1][r]+\text{cost}
\right)
$$
其中：
$$
l\le k<r
$$
如果求最小值：
dp[l][r] = min(...)
如果求最大值：
dp[l][r] = max(...)
五、为什么必须按照区间长度计算？¶
这是区间 DP 最重要的代码结构之一。
假设：
dp[l][r]
依赖：
dp[l][k]
dp[k+1][r]
那么两个子区间：
[l,k]
[k+1,r]
都比：
[l,r]
短。
所以必须：
先计算短区间，再计算长区间。
通常写成：
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
...
}
}
这就是：
区间 DP 的标准枚举顺序¶
六、第一道经典题：石子合并¶
这是学习区间 DP 最经典的入门题之一。
题目描述¶
有 n 堆石子排成一排：
a1 a2 a3 ... an
每次只能合并相邻的两堆石子。
合并两堆石子的代价为：
两堆石子的石子总数。
求将所有石子合并成一堆的最小总代价。
示例¶
4
1 3 5 2
一种合并方法：
1 3 5 2
1+3 = 4
4 5 2
4+5 = 9
9 2
9+2 = 11
11
总费用：
$$
4+9+11=24
$$
但是不同的合并顺序可能得到不同的总代价。
我们需要求最小值。
七、石子合并为什么适合区间 DP？¶
观察最终过程：
[1, n]
最终一定是由某两个区间合并得到：
[1, k]
[k+1, n]
也就是说：
整个区间
↓
左区间 + 右区间
因此自然想到：
$$
dp[l][r]
$$
八、状态定义¶
定义：
$$
dp[l][r]
$$
表示：
将第
l堆到第r堆石子合并成一堆的最小代价。
九、如何进行状态转移？¶
假设最后一次合并：
[l, k]
和：
[k+1, r]
那么：
第一步¶
先把：
[l,k]
合并成一堆。
代价：
$$
dp[l][k]
$$
第二步¶
把：
[k+1,r]
合并成一堆。
代价：
$$
dp[k+1][r]
$$
第三步¶
最后合并这两堆。
这次的代价是多少？
就是整个区间的石子总数：
$$
sum[l][r]
$$
因此：
$$
dp[l][r]
=
\min_{l\le k<r}
\left(
dp[l][k]+dp[k+1][r]+sum[l][r]
\right)
$$
这就是石子合并的核心转移。
十、为什么需要前缀和？¶
每次计算：
$$
sum[l][r]
$$
如果都重新累加：
a[l] + a[l+1] + ... + a[r]
会浪费大量时间。
所以使用前缀和：
$$
prefix[i]=a_1+a_2+\cdots+a_i
$$
那么：
$$
sum[l][r]
=
prefix[r]-prefix[l-1]
$$
于是区间和可以：
$$
O(1)
$$
计算。
十一、石子合并的初始化¶
当：
l == r
表示只有一堆石子。
不需要合并。
因此：
$$
dp[l][l]=0
$$
这也是非常典型的区间 DP 初始化：
长度为 1 的区间通常是最基础状态。
十二、完整 C++ 代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
const long long INF = 4e18;
vector<vector<long long>> dp(
n + 1,
vector<long long>(n + 1, 0)
);
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = INF;
long long sum =
prefix[r] - prefix[l - 1];
for (int k = l; k < r; k++) {
dp[l][r] = min(
dp[l][r],
dp[l][k]
+ dp[k + 1][r]
+ sum
);
}
}
}
cout << dp[1][n] << '\n';
return 0;
}
十三、代码最重要的三层循环¶
一定要理解这三层循环：
for (int len = 2; len <= n; len++)
表示：
枚举区间长度。
for (int l = 1; l + len - 1 <= n; l++)
表示：
枚举左端点。
for (int k = l; k < r; k++)
表示：
枚举最后一次合并的位置。
所以可以把代码翻译成一句话：
枚举区间长度 → 枚举区间位置 → 枚举最后一次分割点。
这是区间 DP 最重要的代码框架。
十四、复杂度分析¶
有：
len：(O(n))l：(O(n))k：(O(n))
因此：
$$
O(n^3)
$$
时间复杂度。
空间：
$$
O(n^2)
$$
十五、第二道经典题：最长回文子序列¶
现在学习一种完全不同的区间 DP。
题目¶
给定一个字符串：
bbbab
求它的最长回文子序列长度。
例如：
bbbb
就是一个回文子序列。
答案：
4
注意：
子序列不要求连续。
十六、什么是回文？¶
例如：
aba
abba
abcba
正着读和反着读一样。
而：
abc
不是回文。
十七、状态设计¶
定义：
$$
dp[l][r]
$$
表示：
字符串区间
[l,r]内的最长回文子序列长度。
十八、观察区间两端¶
考虑：
s[l]
和：
s[r]
有两种情况。
情况一：两端字符相同¶
如果：
$$
s[l]=s[r]
$$
那么这两个字符可以作为回文的两端。
因此：
$$
dp[l][r]
=
dp[l+1][r-1]+2
$$
例如：
b .... b
中间部分如果有最长回文长度 x：
b + 中间回文 + b
长度就是：
$$
x+2
$$
十九、情况二：两端字符不同¶
例如：
a .... b
这两个字符不可能同时作为当前回文的两端。
那么至少有一个端点不能使用。
我们考虑两种情况：
去掉左边
或者：
去掉右边
所以：
$$
dp[l][r]
=
\max(
dp[l+1][r],
dp[l][r-1]
)
$$
二十、完整状态转移¶
因此：
$$
dp[l][r]
=
\begin{cases}
dp[l+1][r-1]+2,&s_l=s_r\
\max(dp[l+1][r],dp[l][r-1]),&s_l\ne s_r
\end{cases}
$$
二十一、初始化¶
当：
l == r
只有一个字符。
一个字符本身就是回文。
所以：
$$
dp[l][l]=1
$$
二十二、为什么仍然要按照长度递增？¶
因为：
dp[l][r]
依赖：
dp[l+1][r-1]
dp[l+1][r]
dp[l][r-1]
这些区间都更短。
所以仍然是：
for (len = 1; len <= n; len++)
二十三、C++ 完整实现¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
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 l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) {
if (len == 2) {
dp[l][r] = 2;
} else {
dp[l][r] =
dp[l + 1][r - 1] + 2;
}
} else {
dp[l][r] = max(
dp[l + 1][r],
dp[l][r - 1]
);
}
}
}
cout << dp[0][n - 1] << '\n';
return 0;
}
二十四、代码可以进一步简化吗？¶
可以。
如果：
s[l] == s[r]
而区间长度为 2：
aa
内部为空。
我们可以定义：
$$
dp[l+1][r-1]=0
$$
或者直接使用二维数组边界处理。
为了让初学者更容易理解，上面的代码专门处理了：
if (len == 2)
后面熟练以后，可以写得更简洁。
二十五、第三道经典题：矩阵链乘法¶
这是区间 DP 中非常经典的综合题。
题目¶
有三个矩阵：
$$
A_1,A_2,A_3
$$
它们的维度分别是：
A1：10 × 30
A2：30 × 5
A3：5 × 60
需要计算：
$$
A_1A_2A_3
$$
矩阵乘法满足结合律：
$$
(A_1A_2)A_3
=
A_1(A_2A_3)
$$
但是不同的计算顺序，乘法次数不同。
求最少需要多少次标量乘法。
二十六、为什么计算顺序很重要？¶
先算：
$$
(A_1A_2)A_3
$$
计算：
$$
A_1A_2
$$
需要：
$$
10\times30\times5=1500
$$
结果矩阵：
$$
10\times5
$$
然后：
$$
(10\times5)(5\times60)
$$
需要：
$$
10\times5\times60=3000
$$
总共：
$$
4500
$$
另一种：
$$
A_1(A_2A_3)
$$
先计算：
$$
A_2A_3
$$
需要：
$$
30\times5\times60=9000
$$
结果：
$$
30\times60
$$
再计算：
$$
(10\times30)(30\times60)
$$
需要：
$$
10\times30\times60=18000
$$
总共：
$$
27000
$$
因此第一种明显更优。
二十七、状态设计¶
定义：
$$
dp[l][r]
$$
表示：
计算矩阵 (A_lA_{l+1}\cdots A_r) 所需的最少标量乘法次数。
二十八、如何转移？¶
最后一次计算一定存在一个分割点：
$$
k
$$
把：
$$
A_l\cdots A_r
$$
拆成：
$$
(A_l\cdots A_k)
(A_{k+1}\cdots A_r)
$$
左边：
$$
dp[l][k]
$$
右边：
$$
dp[k+1][r]
$$
最后把两个结果矩阵相乘。
假设矩阵维度数组为：
p
其中：
$$
A_i
$$
的维度为：
$$
p_{i-1}\times p_i
$$
那么最后一次乘法需要：
$$
p_{l-1}\times p_k\times p_r
$$
次标量乘法。
因此：
$$
dp[l][r]
=
\min_{l\le k<r}
\left(
dp[l][k]
+
dp[k+1][r]
+
p_{l-1}p_kp_r
\right)
$$
二十九、初始化¶
只有一个矩阵：
A[i]
不需要进行矩阵乘法。
所以：
$$
dp[i][i]=0
$$
三十、C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// A[i] 的维度为 p[i-1] × p[i]
vector<long long> p(n + 1);
for (int i = 0; i <= n; i++) {
cin >> p[i];
}
const long long INF = 4e18;
vector<vector<long long>> dp(
n + 1,
vector<long long>(n + 1, 0)
);
for (int len = 2; len <= n; len++) {
for (int l = 1;
l + len - 1 <= n;
l++) {
int r = l + len - 1;
dp[l][r] = INF;
for (int k = l; k < r; k++) {
long long cost =
dp[l][k]
+ dp[k + 1][r]
+ p[l - 1] * p[k] * p[r];
dp[l][r] =
min(dp[l][r], cost);
}
}
}
cout << dp[1][n] << '\n';
return 0;
}
三十一、三道区间 DP 的共同结构¶
现在把三个问题放到一起。
| 问题 | 状态 | 分割/决策 | 求什么 |
|---|---|---|---|
| 石子合并 | dp[l][r] |
最后一次合并位置 k |
最小代价 |
| 最长回文子序列 | dp[l][r] |
是否使用左右端点 | 最大长度 |
| 矩阵链乘法 | dp[l][r] |
最后一次乘法位置 k |
最小代价 |
虽然题目完全不同，但核心思想高度相似：
把一个大区间的问题拆成更小的区间问题。
三十二、区间 DP 的核心套路¶
以后看到一个问题，可以按照下面的流程思考。
第一步：确定区间¶
问：
当前问题是不是针对连续的一段？
如果是，考虑：
$$
dp[l][r]
$$
第二步：确定状态含义¶
例如：
dp[l][r] = 区间 [l,r] 的最小代价
或者：
dp[l][r] = 区间 [l,r] 的最长回文长度
一定要把这句话说完整。
第三步：寻找最后一次操作¶
这是区间 DP 最重要的思维。
问：
假设整个区间最终已经解决，那么最后一步是什么？
例如石子合并：
最后一次合并
矩阵链：
最后一次矩阵乘法
然后找到：
k
将大区间拆成：
[l,k]
[k+1,r]
三十三、“最后一步”为什么这么重要？¶
这是 DP 中非常经典的思维方式。
假设：
[1,10]
最终完成。
我们不知道整个过程到底是什么。
但是我们可以问：
最后一步发生了什么？
假设最后一步把：
[1,k]
和：
[k+1,10]
合并。
那么在最后一步发生之前：
[1,k]
已经是一个完整答案。
[k+1,10]
也已经是一个完整答案。
于是：
$$
大问题
=
小问题1
+
小问题2
+
最后一步代价
$$
这正是动态规划的核心思想。
三十四、区间 DP 的标准模板¶
以后遇到典型区间 DP，可以先写：
for (int len = 2; len <= n; len++) {
for (int l = 1;
l + len - 1 <= n;
l++) {
int r = l + len - 1;
// 初始化 dp[l][r]
for (int k = l; k < r; k++) {
// dp[l][r]
// 根据 dp[l][k]
// 和 dp[k+1][r]
// 进行转移
}
}
}
这个模板建议熟练到可以脱离提示写出来。
三十五、为什么不能这样写？¶
很多初学者会写：
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
...
}
}
这种写法并不一定错误，但很容易出现：
dp[l][r]依赖的更短区间还没有计算。
例如：
dp[1][5]
可能需要：
dp[2][4]
如果计算顺序不正确，就可能使用尚未得到的状态。
因此初学阶段最推荐：
len → l → k
也就是：
按照区间长度递增。
三十六、区间 DP 的复杂度¶
典型区间 DP：
区间长度：O(n)
左端点：O(n)
分割点：O(n)
因此：
$$
O(n^3)
$$
空间：
$$
O(n^2)
$$
这也是为什么区间 DP 通常适用于：
n ≤ 几百
左右的数据范围。
如果：
n = 10^5
还需要进一步寻找特殊结构和优化方法。
三十七、一个非常重要的“DP 五问法”¶
从今天开始，遇到任何 DP 题，都建议学生强迫自己回答这五个问题：
① 状态是什么？¶
例如：
$$
dp[l][r]
$$
② 状态表示什么？¶
一定要用完整中文说出来。
③ 初始状态是什么？¶
例如：
$$
dp[i][i]=0
$$
或者：
$$
dp[i][i]=1
$$
④ 当前状态从哪里来？¶
也就是：
转移方程是什么？
⑤ 按什么顺序计算？¶
例如：
len 从小到大
如果这五个问题都能够回答，DP 基本就已经入门了。
三十八、三类 DP 的思维变化¶
到目前为止，我们已经学习了三大类 DP。
第一类：线性 DP¶
核心：
dp[i]
典型问题：
- 最长上升子序列
- 最大子段和
- 打家劫舍
- 字符串问题
核心思维：
当前状态从前面的哪些状态转移而来？
第二类：背包 DP¶
核心：
dp[j]
典型问题：
- 01 背包
- 完全背包
- 多重背包
- 分组背包
核心思维：
当前物品能不能选择？可以选择几次？
第三类：区间 DP¶
核心：
dp[l][r]
典型问题：
- 石子合并
- 矩阵链乘法
- 回文问题
核心思维：
大区间的最后一步是什么？如何拆成小区间？
三十九、阶段性知识地图¶
动态规划
│
┌───────────────┼────────────────┐
│ │ │
线性DP 背包DP 区间DP
│ │ │
dp[i] dp[j] dp[l][r]
│ │ │
↓ ↓ ↓
LIS 01背包 石子合并
LCS 完全背包 回文子序列
编辑距离 多重背包 矩阵链乘法
分组背包
现在我们已经完成了动态规划的第一阶段基础框架。
四十、课后必须完成的训练¶
建议不要只做“看懂”，而要进行手算 → 写转移 → 写代码 → 调试四步训练。
题目 1：石子合并¶
输入：
4
1 3 5 2
要求：
- 手动画出
dp[l][r]。 - 计算
dp[1][2]。 - 计算
dp[2][4]。 - 计算
dp[1][4]。 - 写 C++。
题目 2：最长回文子序列¶
输入：
bbbab
要求：
- 写出
dp[l][r]的定义。 - 写出字符相同时的转移。
- 写出字符不同时的转移。
- 手算最终答案。
- 修改程序，使其输出一个最长回文子序列。
题目 3：矩阵链乘法¶
矩阵：
A1：10 × 30
A2：30 × 5
A3：5 × 60
要求：
- 计算
(A1A2)A3的代价。 - 计算
A1(A2A3)的代价。 - 写出
dp[1][3]。 - 写 C++ 程序。
四十一、下一讲：树形 DP¶
接下来进入动态规划中一个非常重要的分支：
第五讲：树形 DP¶
我们会从最基础的树开始：
1
/ | \
2 3 4
/ \
5 6
学习为什么树形 DP 通常需要：
dfs(u, father)
以及：
$$
dp[u][0]
$$
$$
dp[u][1]
$$
这样的状态。
重点学习三道经典题：
- 树的最大独立集 / 没有上司的舞会
- 树上背包
- 树的直径相关 DP
并重点解决一个学生经常遇到的问题：
为什么树形 DP 可以使用 DFS？DFS 和 DP 到底是什么关系？
随后我们再进入：
DAG 上的 DP → 状态压缩 DP → 数位 DP → 概率 DP → DP 优化。
这样最终可以建立一套比较完整的中学生竞赛动态规划知识体系。