本篇内容介绍了区间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 参考书籍
有话要说...