??区间DP又名区间动态规划，在 LeetCode 上属于难度中上的题，而 ACM 竞赛中属于简单级别，为必须掌握的内容。实际思想也比较简单，基本上看完我写的总结，大部分题目都可以用模板套出来了。 ??区间DP的状态设计相对简单，基本大部分问题都是用
f
[
i
]
[
j
]
f[i][j]
f[i][j] 代表区间
[
i
，
j
]
[i，j]
[i，j] 上的最优解。难点在于状态转移的设计上。本文将通过一些例题，详细讲解常见的状态转移套路。 ??对于区间DP来说，一个最经典的思想就是正难则反，听我娓娓道来。
二、石子归并
石子归并问题，基本上是所有讲解 区间 DP 的文章都会提到的一个题，那么我也不例外。
【例题1】有
n
(
n
≤
100
)
n(n \le 100)
n(n≤100) 堆石子摆放成一排，第
i
i
i 堆的重量为
w
i
w_i
wi?，现要将石子有次序地合并成一堆。规定每次只能选相邻的二堆合并成新的一堆，合并的消耗为当前合并石子的总重量。试设计出一个算法，计算出将
n
n
n 堆石子合并成一堆的最小消耗。
我们发现这个问题的难点在于：当选出的两堆石子合并以后，它的重量变成了合并后的和，对于
n
n
n 堆石子，选择的
n
?
1
n-1
n?1 种合并方式，到达的都是不同的状态，无法进行状态存储。
2、正难则反
当没有头绪的时候，我们试着将问题反过来思考；
我们发现这棵深度优先搜索树的所有叶子结点都是一样的，这就为我们解决问题带来了突破口；
对于
[
1
,
n
]
[1, n]
[1,n] 堆石子，假设已经合并了
n
?
2
n-2
n?2 次，必然只剩下 二堆石子，那么我们只需要合并最后一次，就可以把两堆石子变成一堆，假设合并最后一次的位置发生在
k
k
k，也就是最后剩下两堆分别为：
[
1
,
k
]
[1, k]
[1,k] 和
[
k
+
1
,
n
]
[k+1, n]
[k+1,n]，如图二-2-1所示：
图二-2-1
注意，这个时候
[
1
,
k
]
[1, k]
[1,k] 和
[
k
+
1
,
n
]
[k+1, n]
[k+1,n] 已经各自合并成一堆了，所以我们把问题转换成了求
[
1
,
k
]
[1, k]
[1,k] 合并一堆的最小消耗，以及
[
k
+
1
,
n
]
[k+1, n]
[k+1,n] 合并成一堆的最小消耗；而这里
k
k
k 的取值范围为
[
1
,
n
?
1
]
[1, n-1]
[1,n?1]；
利用这样的方法，逐步将区间缩小成 1，就可以得到整个问题的解了。
3、设计状态
令
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示从 第
i
i
i 堆 石子到 第
j
j
j 堆 石子合并成一堆所花费的最小代价。
4、状态转移方程
f
[
i
]
[
j
]
=
{
0
i
=
j
min
?
k
=
i
j
?
1
(
f
[
i
]
[
k
]
+
f
[
k
+
1
]
[
j
]
+
c
o
s
t
(
i
,
j
)
)
i
≠
j
f[i][j] = \begin{cases} 0 & i=j\\ \min_{k=i}^{j-1}(f[i][k] + f[k+1][j] + cost(i,j)) & i \neq j\end{cases}
f[i][j]={0mink=ij?1?(f[i][k]+f[k+1][j]+cost(i,j))?i=ji?=j?
其中
c
o
s
t
(
i
,
j
)
=
∑
k
=
i
j
w
k
cost(i, j) = \sum_{k=i}^{j}w_k
cost(i,j)=∑k=ij?wk?
有了上面 “正难则反” 的解释，这个状态转移方程就很好理解了；
1）当
i
=
j
i=j
i=j 时，由于
f
[
i
]
[
j
]
f[i][j]
f[i][j] 已经是一堆了，所以消耗自然就是 0 了；
2）当
i
≠
j
i \neq j
i?=j 时，我们需要把目前剩下的两堆合并成一堆，一堆是
f
[
i
]
[
k
]
f[i][k]
f[i][k] ，另一堆是
f
[
k
+
1
]
[
j
]
f[k+1][j]
f[k+1][j]，这两堆合并的消耗就是 从 第
i
i
i 堆到第
j
j
j 堆的重量之和，即
c
o
s
t
(
i
,
j
)
=
∑
k
=
i
j
w
k
cost(i, j) = \sum_{k=i}^{j}w_k
cost(i,j)=∑k=ij?wk?，而对于合并方案，总共
k
=
j
?
i
k=j-i
k=j?i 种选择，所以枚举
j
?
i
j-i
j?i 次，取其中最小值就是答案了。
通过记忆化搜索求解
f
[
1
]
[
n
]
f[1][n]
f[1][n] 就是最后的答案。
以上就是最经典的区间 DP 问题。
三、区间DP的特征
1、状态设计
利用区间来描述状态，所以一般情况下都可以用
f
[
i
]
[
j
]
f[i][j]
f[i][j] 作为 DP 数组，其中
i
,
j
i, j
i,j 为问题对应的区间
[
i
,
j
]
[i, j]
[i,j] 的左右端点；
当然，有的时候需要一个辅助维，状态可能会设计成
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] ，其中
i
,
j
i, j
i,j 为问题对应的区间
[
i
,
j
]
[i, j]
[i,j] 的左右端点，而
k
k
k 因题而已，这个在下文 区间DP的进阶 这一节里会讲到。
2、状态转移
状态转移一定是从 区间长度短 的状态 到 区间长度长 的状态；
3、时间复杂度
涉及到利用 区间DP 来求解的问题，一般都有一个对应的序列：
1）当序列的长度为
n
≤
300
n \le 300
n≤300 时，区间DP 的时间复杂度一般为
O
(
n
3
)
O(n^3)
O(n3)，其中 状态转移时间复杂度 为
O
(
n
)
O(n)
O(n)；
2）当序列的长度为
n
≤
1000
n \le 1000
n≤1000 时，区间DP 的时间复杂度一般为
O
(
n
2
)
O(n^2)
O(n2)，其中 状态转移时间复杂度 为
O
(
1
)
O(1)
O(1)；
对于一个序列，最后一定会经过
n
?
2
n-2
n?2 次删除数字变成只剩下首尾两个数的情况，即：
图四-1-3
那么根据 “正难则反” 的思想，我们不去考虑第一个删除的数，而是考虑最后一个被删除的数的情况；
令最后一个被删除的数是
a
k
a_k
ak?，情况如下：
图四-1-4
也就是说，如果最后一个被删除的是
a
k
a_k
ak?，那么消耗就是
a
1
a
k
a
n
a_1 a_k a_n
a1?ak?an?，那么对于
[
1...
k
]
[1 ... k]
[1...k] 和
[
k
.
.
.
n
]
[k ... n]
[k...n] 这两个区间，前者需要删除
k
?
2
k-2
k?2 个数，后者需要删除
n
?
k
?
1
n-k-1
n?k?1 个数，并且两个端点的数是不能被删除的。
这样就把原本大区间的问题，转换成了两个小区间的问题。
令
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示区间
[
i
,
j
]
[i, j]
[i,j] 中的数删除除端点外的所有数得到的最小消耗，则有状态转移方程如下：
f
[
i
]
[
j
]
=
{
0
j
?
i
≤
1
min
?
k
=
i
+
1
j
?
1
(
f
[
i
]
[
k
]
+
f
[
k
]
[
j
]
+
a
i
a
k
a
j
)
j
?
i
>
1
f[i][j] = \begin{cases}0 & j-i \le 1\\ \min_{k=i+1}^{j-1}(f[i][k] + f[k][j] + a_i a_k a_j) & j-i \gt 1\end{cases}
f[i][j]={0mink=i+1j?1?(f[i][k]+f[k][j]+ai?ak?aj?)?j?i≤1j?i>1?
f
[
1
]
[
n
]
f[1][n]
f[1][n] 即为最后的答案。
2、代码实现
1）递归实现
比较直观的求解 区间DP 的方法是记忆化搜索，只要想好递归出口 和 状态转移，基本就是套模板了。
intdfs(int l,int r){if(l +1== r){return0;// 1)}int&val = f[l][r];if(val != inf){// 2)return val;}
val =1e9;for(int k = l +1; k < r;++k){int v =dfs(l, k)+dfs(k, r)+ a[l]* a[k]* a[r];
val =min(val, v);// 3)}return val;}
1）当区间长度为 2 的时候，无需进行删除，已经到达递归出口，所以消耗为 0；
2）初始化所有区间状态值为
f
[
l
]
[
r
]
=
i
n
f
f[l][r] = inf
f[l][r]=inf，如果不等于这个值，说明已经计算出来了，则无需递归计算，直接返回已经计算出来的值即可；
for(int len =1; len <= n;++len){for(int l =1; l + len -1<= n;++l){int r = l + len -1;// 1)if(len ==1|| len ==2){
f[l][r]=0;// 2)continue;}
f[l][r]=1e9;for(int k = l +1; k < r;++k){int v = f[l][k]+ f[k][r]+ a[l]* a[k]* a[r];
f[l][r]=min(f[l][r], v);// 3)}}}
1）优先枚举区间长度
l
e
n
len
len，再枚举左端点
l
l
l，这样区间右端点就可以通过两者计算出来：
r
=
l
+
l
e
n
?
1
r = l + len - 1
r=l+len?1，并且保证了状态转移的方向一定是从小区间到大区间；
【例题3】有
n
(
n
≤
100
)
n(n \le 100)
n(n≤100) 堆石子摆放成一圈，第
i
i
i 堆的重量为
w
i
w_i
wi?，现要将石子有次序地合并成一堆。规定每次只能选相邻的二堆合并成新的一堆，合并的消耗为当前合并石子的总重量。试设计出一个算法，计算出将
n
n
n 堆石子合并成一堆的最小消耗。
这个问题和 【例题1】 的区别在于原本的链状结构变成了环状结构，我们可以将石子拷贝一份同样的数据，即令
w
n
+
i
=
w
i
w_{n+i} = w_i
wn+i?=wi?，将原来的长度为
n
n
n 的序列变成
2
n
2n
2n，然后枚举左端点
l
∈
[
1
,
n
]
l \in [1,n]
l∈[1,n]，做
n
n
n 次区间 DP，然后再取最小值，时间复杂度
O
(
n
4
)
O(n^4)
O(n4)。
注意到这里计算
[
l
,
l
+
n
]
[l, l+n]
[l,l+n] 和
[
l
+
1
,
l
+
1
+
n
]
[l+1, l+1+n]
[l+1,l+1+n] 区间DP 的最优值时，
[
l
+
1
,
l
+
n
]
[l+1, l+n]
[l+1,l+n] 这段区间是两者的重叠区间，所以这里同样是可以记忆化的，即可以把
n
n
n 次 区间DP 放在一起做（即只需要一次初始化），然后求：
min
?
(
f
[
1
]
[
n
]
,
f
[
2
]
[
1
+
n
]
,
.
.
.
,
f
[
n
]
[
2
n
?
1
]
)
\min( f[1][n], f[2][1+n], ..., f[n][2n-1])
min(f[1][n],f[2][1+n],...,f[n][2n?1])
就是最后的答案了，这时候，时间复杂度是
O
(
n
3
)
O(n^3)
O(n3) 的。
2、回文子序列
【例题4】给定一个
n
(
n
≤
1000
)
n( n \le 1000)
n(n≤1000) 个元素
a
i
a_i
ai? 的序列，求它的最长的回文子序列的长度。
令
f
[
i
]
[
j
]
f[i][j]
f[i][j] 为第
i
i
i 个元素到第
j
j
j 个元素的最长回文子序列的长度，考虑以下几个情况：
1）
i
>
j
i \gt j
i>j：这个时候代表它是个空串，所以最长回文子序列的长度肯定为 0；
2）
i
=
j
i=j
i=j：对于长度为 1 的串，本身就是一个回文序列，所以最长回文子序列的长度为 1；
3）
i
<
j
，
a
i
≠
a
j
i < j，a_i \neq a_j
i<j，ai??=aj?：由于区间端点的两个元素值不相等，所以
f
[
i
]
[
j
]
f[i][j]
f[i][j] 不可能比
f
[
i
+
1
]
[
j
]
f[i+1][j]
f[i+1][j] 或者
f
[
i
]
[
j
?
1
]
f[i][j-1]
f[i][j?1] 更长，至多和两者的大者相等，即
f
[
i
]
[
j
]
=
max
?
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
?
1
]
)
f[i][j] = \max(f[i+1][j], f[i][j-1])
f[i][j]=max(f[i+1][j],f[i][j?1])，这样就把区间缩小了；
4）
i
<
j
，
a
i
=
a
j
i < j，a_i = a_j
i<j，ai?=aj?：由于区间端点的两个元素值相等，所以只需要知道这两个元素包围的区间的最大值，即
f
[
i
+
1
]
[
j
?
1
]
f[i+1][j-1]
f[i+1][j?1]，再加上 2 就是包含两端点的最长回文子序列的长度；那么当然还要考虑不包含的情况，也就是（3）的情况；
于是，可以得出状态转移方程如下：
f
[
i
]
[
j
]
=
{
0
i
>
j
1
i
=
j
max
?
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
?
1
]
)
i
<
j
,
a
i
≠
a
j
max
?
{
f
[
i
+
1
]
[
j
?
1
]
+
2
f
[
i
+
1
]
[
j
]
f
[
i
]
[
j
?
1
]
i
<
j
,
a
i
=
a
j
f[i][j] = \begin{cases}0 & i > j \\ 1 & i=j \\ \max(f[i+1][j], f[i][j-1]) & i < j, a_i \neq a_j \\ \max \begin{cases} f[i+1][j-1] + 2 \\ f[i+1][j] \\ f[i][j-1] \end{cases} & i < j, a_i = a_j\end{cases}
f[i][j]=????????????????????01max(f[i+1][j],f[i][j?1])max??????f[i+1][j?1]+2f[i+1][j]f[i][j?1]??i>ji=ji<j,ai??=aj?i<j,ai?=aj??
首先对于这个问题，本身已经连在一起的方块一定是一起消除的，所以首先一定要预处理输入，将相同颜色的方块归并，
c
o
l
o
r
i
color_i
colori? 表示第
i
i
i 种方块的颜色，
n
u
m
i
num_i
numi? 表示第
i
i
i 种方块的数量；
那么如果用
f
[
i
]
[
j
]
f[i][j]
f[i][j] 来表示区间
[
i
,
j
]
[i, j]
[i,j] 下能够消除得到的最大分数，我们发现无法进行状态转移，因为如果
i
i
i 和
j
j
j 能够放在一起消除的条件是
[
i
+
1
,
j
?
1
]
[i+1, j-1]
[i+1,j?1] 的区间上都已经被消除，但是从这个状态表示上并不能体现，所以，我们需要增加一维来表示状态。
令
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] 表示
[
i
,
j
]
[i, j]
[i,j] 消除，并且第
j
j
j 个块连同后面
k
k
k 个颜色相同块消去的最大分数；
1）第
j
j
j 个块单独和后面的
k
k
k 个块消掉，那么分数为
f
[
i
]
[
j
?
1
]
[
0
]
+
(
n
u
m
j
+
k
)
2
f[i][j-1][0] + (num_j+k)^2
f[i][j?1][0]+(numj?+k)2 ；
2）对于
s
∈
[
i
,
j
)
s \in [i, j)
s∈[i,j)，如果
c
o
l
o
r
s
=
c
o
l
o
r
j
color_s = color_j
colors?=colorj?，那么如果我们要把他们在后续归并到一起，势必中间的
(
s
,
j
)
(s, j)
(s,j) 这些块要单独计算，其最大值为
f
[
s
+
1
]
[
j
?
1
]
[
0
]
f[s+1][j-1][0]
f[s+1][j?1][0]；并且，为
[
i
,
s
]
[i,s]
[i,s] 这个区间的最后一种类型的块，增加了
n
u
m
j
num_j
numj? 个，即最大值为
f
[
i
]
[
s
]
[
n
u
m
j
+
k
]
f[i][s][ num_j+k ]
f[i][s][numj?+k]，则有:
f
[
i
]
[
s
]
[
n
u
m
j
+
k
]
+
f
[
s
+
1
]
[
j
?
1
]
[
0
]
f[i][s][ num_j + k ] + f[s+1][j-1][0]
f[i][s][numj?+k]+f[s+1][j?1][0]
联合（1） 和 （2）得出状态转移方程：
f
[
i
]
[
j
]
=
max
?
{
f
[
i
]
[
j
?
1
]
[
0
]
+
(
n
u
m
j
+
k
)
2
f
[
i
]
[
s
]
[
n
u
m
j
+
k
]
+
f
[
s
+
1
]
[
j
?
1
]
[
0
]
c
o
l
o
r
s
=
c
o
l
o
r
j
f[i][j] = \max \begin{cases} f[i][j-1][0] + (num_j+k)^2 \\ f[i][s][ num_j + k ] + f[s+1][j-1][0] & color_s = color_j\end{cases}
f[i][j]=max{f[i][j?1][0]+(numj?+k)2f[i][s][numj?+k]+f[s+1][j?1][0]?colors?=colorj??
