当前位置:首页 > 教育 > 正文

算法竞赛专题解析│区间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

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

按自顶向下的思路分析状态转移方程,很容易理解。计算大区间[i,j]的最优值时,合并它的两个子区间[i,k]和[k+1,j],对所有可能的合并(i≤k

编程用自底向上递推的方法,先在小区间进行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

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

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

for( intk=i;k

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

dp[i][j] = INF;

for( intk=i; 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

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

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

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

输出:对每个用例,输出最小愤怒值之和。

题解:

读者可以试试用栈来模拟,非常困难。这是一道区间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

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

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

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

参考书籍

你可能想看:

有话要说...

取消
扫码支持 支付码