算法竞赛专题解析│区间DP

本篇内容介绍了区间DP的概念以及其2种模板代码，并且提供了区间DP的经典例题、二维区间DP。

*本文内容由罗勇军老师提供。

01

概念和模板代码

区间DP是常见的DP应用场景。

经典例子是“石子合并”问题，用这个例子解释区间DP的概念，并给出两种模板代码。

石子合并

题目描述：有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。

输入：第一行是整数n，表示有n堆石子。第二行有n个数，分别表示这n堆石子的数目。

输出：总的最小花费。

输入样例：

3

2 4 5

输出样例：

17

提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17。

定义dp[i][j]为合并第i堆到第j堆的最小花费。状态转移方程是：

dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]}   i≤k<j

dp[1][n]就是答案。方程中的w[i][j]表示从第i 堆到第j 堆的石子总数。

按自顶向下的思路分析状态转移方程，很容易理解。计算大区间[i,j]的最优值时，合并它的两个子区间[i,k]和[k+1,j]，对所有可能的合并（i≤k<j，即k 在i、j之间滑动），返回那个最优的合并。子区间再继续分解为更小的区间，最小的区间[i,i+1]只包含两堆石子。

编程用自底向上递推的方法，先在小区间进行DP得到最优解，然后再逐步合并小区间为大区间。下面给出求ddp[i][j]的代码，其中包含i、j、k的3层循环，时间复杂度O(n 3 )。第一个循环j 是区间终点，第2个循环i 是区间起点，第3个循环k 在区间内滑动。注意，起点i 应该从j−1开始递减，也就是从最小的区间[j−1,j]开始，逐步扩大区间。i 不能从1 开始递增，那样就是从大区间到小区间了。

区间DP的第1种代码

for( inti= 1; i<=n; i++) //n：石子堆数

dp[i][i] = 0; //初始化

for( intj= 2; j<=n; j++) // 区间[i,j]的终点j，i<j<=n

for( inti=j -1;i>= 1;i--) { // 区间[i,j]的起点i

dp[i][j]=INF; //初始化为极大值

for( intk=i;k<j;k++) //大区间[i,j]从小区间[i,k]和[k+1,j]转移而来

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+ 1][j] + w[i][j]);

下面给出另外一种写法，它的i、j、k都是递增的，更容易理解， 推荐使用。其中用了一个辅助变量len，它等于当前处理的区间[i,j]的长度。dp[i][j]是大区间，它需要从小区间dp[i][k]和dp[k+1][j]转移而来，所以应该先计算出小区间，才能根据小区间算出大区间。len就起到了这个作用，从最小的区间len=2开始，此时区间[i,j]等于[i,i+1]；最后是最大区间len=n，此时区间[i,j]等于[1,n]。

区间DP的第2种代码（模板）

for( inti= 1; i<=n; i++)

dp[i][i] = 0;

for( intlen= 2; len<=n; len++) //len：区间[i,j]的长度，从小区间扩展到大区间

for( inti= 1; i<=n- len+ 1; i++){ // 区间起点i

intj = i + len- 1; // 区间终点j，i<j<=n

dp[i][j] = INF;

for( intk=i; k<j; k++)

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);

区间DP的优化。上述代码的复杂度是O(n 3 )，区间DP常常可以用“四边形不等式”进行优化，把复杂度提升到O(n 2 )，详情见前面博文“四边形不等式”。经典例题“石子合并”也在这一篇进行了更详细的讲解。当然，不是所有的区间DP都能这样优化。

下面给出2个经典例题。请读者在看题解之前，自己思考并写出代码，一定会大有收获。

02

例题

1.hdu 2476

String painter

题目描述：给定两个长度相等的字符串A、B，由小写字母组成。一次操作，允许把A中的一个连续子串（区间）都转换为某个字符（就像用刷子刷成一样的字符）。要把A转换为B，问最低操作数是多少?

输入：第一行是字符串A，第二行是字符串B。两个字符串的长度不大于100。

输出：一个表示答案的整数。

输入样例：

zzzzzfzzzzz

abcdefedcba

输出样例：

6

提示：第1次把zzzzzfzzzzz转换为aaaaaaaaaaa，第2次转为abbbbbbbbba，第3次转为abccccccccba…

题解：

这道经典题，能帮助读者深入理解区间DP是如何构造和编码的。

（1）从空白串转换到B

先考虑简单一点的问题：从空白串转换到B。为方便阅读代码，把字符串存储为B[1]~B[n]，不从0开始，编码的时候这样输入：scanf("%s%s", A+1, B+1)。

如何定义DP状态？可以定义dp[i]，表示在区间[1,i]内转换为B的最少步数。或者更进一步，定义dp[i][j]，表示在区间[i , j ]内从空白串转换到B时的最少步数。重点是区间[i,j]两端的字符B[i] 和B[j]，分析以下两种情况。

  1）若B[i] = B[j]。第一次刷用B[i]把区间[i , j]刷一遍，这个刷法肯定是最优的。如果分别去掉两个端点，得到2个区间[i+1,j]、[i,j−1]，这2个区间的最小步数相等，也等于原区间[i,j]的最小步数。例如B[i,j]=“abbba”，先用"a"全部刷一遍，再刷1次"bbb"，共刷2次。如果去掉第一个"a"，剩下的"bbba"，也是刷2次。

  2）若B[i] ≠ B[j]。因为两端点不等，至少要各刷1次。用标准的区间操作，把区间分成[i,k]和[k+1,j]两部分，枚举最小步数。

下面是hdu 2476的代码，其中“从空白串转换到B”的代码完全套用了“石子合并”问题的编码。

# include<bits/stdc++.h>

usingnamespacestd;

charA[ 105],B[ 105];

intdp[ 105][ 105];

constintINF = 0x3f3f3f3f;

intmain{

while(~ scanf( "%s%s", A+ 1, B+ 1)){ //输入A, B

intn = strlen(A+ 1);

for( inti= 1;i<=n;i++)

dp[i][i]= 1; //初始化

//先从空白串转换到B

for( intlen= 2; len<=n; len++)

for( inti= 1; i<=n-len+ 1; i++){

intj = i + len -1;

dp[i][j] = INF;

if(B[i] == B[j]) //区间[i, j]两端的字符相同B[i] = B[j]

dp[i][j] = dp[i+ 1][j]; //或者 = dp[i][j-1])

else//区间[i, j]两端的字符不同B[i] ≠ B[j]

for( intk=i; k<j; k++)

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+ 1][j]);

//下面从A转换到B

for( intj= 1; j<=n; ++j){

if(A[j] == B[j])

dp[ 1][j] = dp[ 1][j -1]; //字符相同不用转

else

for( intk= 1; k<j; ++k)

dp[ 1][j] = min(dp[ 1][j], dp[ 1][k] + dp[k+ 1][j]);

printf( "%d\n",dp[ 1][n]);

return0;

（2）从A转换到B

如何求dp[1][j]？观察A和B相同位置的字符，分析以下两种情况.

  1）若A[j] = B[j]。这个字符不用转换，有dp[1][j] = dp[1][j−1]。

  2）若A[j] ≠ B[j]。仍然用标准的区间DP，把区间分成[1,k]和[k+1,j]两部分，枚举最小步数。这里利用了上一步从空白转换到B的结果，当区间[k+1,j]内A和B的字符不同时，从A转到B，与从空白串转换到B是等价的。

2. hdu 4283

You Are the One

题目描述：n个男孩去相亲，排成一队上场。大家都不想等，排队越靠后越愤怒。每人的耐心不同，用D表示火气，设男孩i的火气是D i ，他排在第k 个时，愤怒值是(k − 1 ) ∗ D i 。

导演不想看到会场气氛紧张。他安排了一个黑屋，可以调整这排男孩上场的顺序，屋子很狭长，先进去的男孩最后出来（黑屋就是一个堆栈）。例如，当男孩A排到时，如果他后面的男孩B火气更大，就把A送进黑屋，让B先上场。一般情况下，那些火气小的男孩要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第二个，而最后一个男孩脾气最坏，导演为了让这个刺头第一个上场，把其他人全赶进了黑屋，结果你就排在了黑屋的第1名，第二个上场相亲了。

注意，每个男孩都要进出黑屋。

对所有男孩的愤怒值求和，求所有可能情况的最小和。

输入：第一行包含一个整数T，即测试用例的数量。对于每种情况，第一行是n（0 <n <= 100），后面n行，整数D 1 -D n 表示男孩的火气值（0 <= D i <= 100）。

输出：对每个用例，输出最小愤怒值之和。

题解：

读者可以试试用栈来模拟，非常困难。这是一道区间DP，巧妙地利用了栈的特性。

定义dp[i][j]，表示从第i 个人到第j 个人，即区间[i,j]的最小愤怒值之和。

由于栈的存在，这一题的区间[i,j]的分割点k 比较特殊。分割时，总是用区间[i,j]的第一个元素i把区间分成两部分，让i 第k 个从黑屋出来上场相亲，即第k 个出栈。根据栈的特性：若第一个元素i 第k 个出栈，则第二到k−1个元素肯定在第一个元素之前出栈，第k+1到最后一个元素肯定在第k 个之后出栈。

例如，5个人排队序号是1、2、3、4、5。如果要第1（i=1）个人第3（k=3）个出场，那么栈的操作是这样：1进栈、2进栈、3进栈、3出栈、2出栈，1出栈。2号、3号在1号之前出栈，1号第3个出栈，4号5号在1号后面出栈。

分割点k（1≤ k≤j-i+1）把区间划分成了两段，即dp[i+1][i+k−1]和dp[i+k][j]。dp[i][j]的计算分为三部分：

（1）dp[i + 1][i+k−1]。原来i后面的k−1个人，现在排到i ii前面了。

（2）第i个人往后挪了k−1个位置，愤怒值加上D[i]*(k−1)。

（3）dp[i + k][j] +k∗(sum[j]−sum[i+k−1])。第k个位置后面的人，即区间[i+k,j]的人，由于都在前k个人之后，相当于从区间的第1个位置往后挪了k个位置，所以整体愤怒值要加上k∗(sum[j]−sum[i+k−1])。其中

是1~j所有人D值的和，sum[j]−sum[i+k−1]是区间[i+k,j]内这些人的D值和。

代码完全套用“石子合并”的模板。其中DP方程给出了两种写法，对照看更清晰。

for( intlen= 2; len<=n; len++)

for(i= 1;i<=n- len+ 1;i++) {

j = len+ i - 1;

dp[i][j] = INF;

for( intk= 1;k<=j-i+ 1;k++) //k：i往后挪了k位。这样写容易理解

dp[i][j] = min(dp[i][j], dp[i+ 1][i+k -1] + D[i]*(k -1)

+ dp[i+k][j] + k*(sum[j]-sum[i+k -1])); //DP方程

//for(int k=i;k<=j;k++) //或者这样写。k是整个队伍的绝对位置

// dp[i][j] = min(dp[i][j], dp[i+1][k] + D[i]*(k-i)

+ dp[k+ 1][j] + (k-i+ 1)*(sum[j]-sum[k]));

3. 二维区间DP

前面的例子的区间[i,j]可以看成在一条直线上移动，即一维DP。这里给出一个二维区间DP的例题，它的区间同时在两个方向移动。

CF1199 F. Rectangle Painting

（提交地址 ）

题目描述：有一个n×n大小的方格图，某些方格初始是黑色，其余为白色。一次操作，可以选定一个h×w的矩形，把其中所有方格涂成白色，代价是max(h, w)。要求用最小的代价把所有方格变成白色。

输入：第1行是整数n，表示方格的大小。后面有n行，每行长度为n的串，包含符号’.‘和’#’，’.‘表示白色，’#'表示黑色。第i行的第j个字符是(i, j)。n ≤ 50。

输出：打印一个整数，表示把所有方格涂成白色的最小代价。

输入样例：

5

输出样例：

5

题解：

设矩形区域从左下角坐标(x1,y1)到右上角坐标(x2,y2)。定义状态dp[x1][y1][x2][y2]，表示把这个区域内染成白色的最小代价。

这个区域可以分别按x轴或者按y轴分割成两个矩形，遍历所有可能的分割，求最小代价。那么从x方向看，就是一个区间DP；从y方向看，也是区间DP。

代码可以完全套用前面一维DP的模板，分别在两个方向操作。

（1）x方向，区间分为[x1,k]和[k+1,x2]。状态转移方程是：

dp[][x1][][x2][] = min([x1][][x2][], dp[x1][][k][] + dp[k+1][][x2][])

（2）y方向，区间分为[y1,k]和[k+1,y2]。状态转移方程是：

dp[][y1][][y2] = min([][y1][][y2], dp[][y1][][k] + dp[][k+1][][y2])

下面的代码有5层循环，时间复杂度O(n 5 )。对比一维区间DP，有3层循环，复杂度是O(n 3 )。

CF1199 F代码

# include<bits/stdc++.h>

usingnamespacestd;

# defineN 55

intdp[N][N][N][N];

charmp[N][N]; //方格图

intmain{

intn; cin>>n;

for( inti= 1;i<=n;i++)

for( intj= 1;j<=n;j++)

cin>>mp[i][j];

for( inti= 1;i<=n;i++)

for( intj= 1;j<=n;j++)

if(mp[i][j]== '.') dp[i][j][i][j]= 0; //白格不用涂

elsedp[i][j][i][j]= 1; //黑格(i,j)涂成白色需1次

for( intlenx= 1;lenx<=n;lenx++) //len从1开始，不是2。因为有x和y两个方向

for( intleny= 1;leny<=n;leny++)

for( intx1= 1;x1<=n-lenx+ 1;x1++)

for( inty1= 1;y1<=n-leny+ 1;y1++){

intx2 = x1+lenx -1; //x1：x轴起点；x2：x轴终点

inty2 = y1+leny -1; //y1：y轴起点；y2：y轴终点

if(x1==x2 && y1==y2) continue; //lenx=1且leny=1的情况

dp[x1][y1][x2][y2] = max( abs(x1-x2), abs(y1-y2)) + 1; //初始值

for( intk=x1;k<x2;k++) //枚举x方向，y不变。区间[x1,k]+[k+1,x2]

dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2],

dp[x1][y1][k][y2]+dp[k+ 1][y1][x2][y2]);

for( intk=y1;k<y2;k++) //枚举y方向，x不变。区间[y1,k]+[k+1,y2]

dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2],

dp[x1][y1][x2][k]+dp[x1][k+ 1][x2][y2]);

cout<< dp[ 1][ 1][n][n];

03

参考书籍