区间DP浅析

动态规划の区间dp

核心思想

将一个序列（或者环）分成一段段的小区间，过求解区间内的最优值（通过枚举分割点），进而将每一段区间合并得出整体的最优值

一般的板子

for(int l=1;l<=len;l++){//枚举长度
    for(int j=1,ends=j+l-1;ends<len;j++,ends=j+l-1){// 枚举起点+终点
        dp[j][ends]=inf; //如果处理的是min问题，需要初始化为inf
        for(int k=1;k<ends;k++){//枚举分割点
            dp[j][ends]=max/min(dp[j][ends],dp[j][k]+dp[k+1][ends]+something);
        }
    }
}

特殊情况下可能用不到上述板子，但整体思路相同，都是用小区间更新大区间

一堆习题（难点在于状态转移方程）

以下习题难度依次上升。。

NOI 1995 石子合并

题意：$N$堆石子摆成一个环，每次可以讲相邻两堆石子合并，合并得分为两堆石子数之和，求只剩一堆时的最终得分的最大值和最小值

题解：首先破链成环，即把环的前$n-1$个元素拼到第$n$个元素后面形成一个$2n-1$的链，这样就能遍历到所有状态

状态转移方程如下

$dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+sum[l\to r])$

其中$sum$是从l到r的所有石子的数目之和

PS：需要注意求最小值时的初始化问题，以及递推完后需要再滚一遍求出所有可能值中的最优值

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int dp1[805][805],dp2[805][805];
int a[4005],sum[4005];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		dp2[i][i]=0;
	}
	for(int i=1;i<=n;i++) sum[i+n]=sum[i+n-1]+a[i];
	
	for(int len=1;len<=n;len++){
		for(int j=1,lens=j+len;lens<2*n&&j<2*n;j++,lens=j+len){
			dp2[j][lens]=inf;
			for(int k=j;k<lens;k++){
				dp2[j][lens]=min(dp2[j][lens],dp2[j][k]+dp2[k+1][lens]+sum[lens]-sum[j-1]);
				dp1[j][lens]=max(dp1[j][lens],dp1[j][k]+dp1[k+1][lens]+sum[lens]-sum[j-1]);
			}
		}
	}
	int ansmin=inf,ansmax=0;
	for(int i=1;i<=n;i++){
		ansmin=min(ansmin,dp2[i][i+n-1]);
		ansmax=max(ansmax,dp1[i][i+n-1]);
	}
	
	cout<<ansmin<<endl<<ansmax<<endl;
	return 0;
}

洛谷 P1063 能量项链

题意：点链接进去看吧

题解：区间dp，直接上状态转移方程

$dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1])$

其中$a_i$代表第$i$个输入的标记值

PS：注意一下dp方程中的下标问题（其实自己举个例子就能推出来是这么个原理）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int n,dp[405][405],a[405];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int len=2;len<=n;len++){//长度最短为2
		for(int j=1,ends=len+j-1;ends<2*n&&j<2*n;j++,ends=len+j-1){
			for(int k=j;k<ends;k++){
				dp[j][ends]=max(dp[j][ends],dp[j][k]+dp[k+1][ends]+a[j]*a[k+1]*a[ends+1]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][i+n-1]);
	cout<<ans<<endl;
	return 0;
}

POJ 1651 Multiplication Puzzle

题意：有一个序列，你可以任意删掉除了首尾之外的一个元素，然后获得该元素与相邻两元素的乘积的分数，求可得到的最小分数

题解：区间dp，状态转移方程如下

$dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])$

PS：注意首尾元素不能取，因此初始长度为3

#include<iostream>
#include<cstdlib>
using namespace std;
const int inf=1<<30;
int n,dp[405][405],a[405];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int len=3;len<=n;len++){// 初始长度最短为3
		for(int j=1,ends=len+j-1;ends<=n;j++,ends=len+j-1){
			dp[j][ends]=inf;
			for(int k=j+1;k<ends;k++){
				dp[j][ends]=min(dp[j][ends],dp[j][k]+dp[k][ends]+a[j]*a[k]*a[ends]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}//https://vjudge.net/problem/POJ-1651

POJ 2955 Brackets

题意：给一串只有()[]这四个字符的字符串，要求求出最长的合法的括号表达式的子序列长度

题解：区间dp，状态转移需要考虑$s[l]$是否和$s[r]$匹配，如果匹配就要加上2，其他的就按照正常的枚举分割点操作来更新

$dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r])\\ if(s[l]==s[r])\ dp[l][r]=dp[l+1][r-1]+2$

AC代码：

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
string s;
int dp[105][105];
int main(){
	while(cin>>s&&s!="end"){
		memset(dp,0,sizeof(dp));
		int len=s.length();
		for(int i=1;i<=len;i++){
			for(int j=0,ends=j+i-1;ends<len;j++,ends=j+i-1){
				if((s[ends]==')'&&s[j]=='(')||(s[ends]==']'&&s[j]=='[')){
					dp[j][ends]=dp[j+1][ends-1]+2;
				}
				for(int k=j;k<ends;k++){
					dp[j][ends]=max(dp[j][ends],dp[j][k]+dp[k][ends]);
				} 
			}	
		}
		cout<<dp[0][len-1]<<endl;
	}
	return 0;
}

洛谷 P1043 数字游戏

题意：有一圈数，现在要求你把它分成非空的m份，计算每一份的和，然后把这些和乘起来，最终的到一个k，求k的最大值和最小值

题解：一看就是个环状的区间dp，但是分成m分这一点稍微有点难考虑，其实也就是dp方程多了一维罢了，状态如下

$dp[i][j][k]:该序列从i到j的区间分成k份所得的最优解$

转移方程如下

$dp[i][j][k]=max(dp[i][j][k],dp[i][h][k-1]*(sum[j]-sum[h]))$

其中$h$为枚举的中间点，$sum$数组为前缀和数组

按照套路，我们的枚举顺序如下：

枚举区间长度
枚举起点+终点
枚举中间点

现在多了一个m份，我们知道中间点的枚举一定是最内层的（因为他要更新答案），那么我们可以把分割成m份的操作放在倒数第二层循环，也就是$ijk$顺序枚举

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int dp1[185][185][115],dp2[185][185][115];
int a[155],sum[155];
int n,m;

inline int giao(int x){
	return (x%10+10)%10;
}
int main(){
	cin>>n>>m;
	memset(dp2,0x3f3f3f,sizeof(dp2));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++) sum[i+n]=sum[i+n-1]+a[i];
	
	for(int i=1;i<=2*n;i++){
		for(int j=i;j<=2*n;j++){
			dp1[i][j][1]=dp2[i][j][1]=giao(sum[j]-sum[i-1]);
		} 
	}
	
	for(int i=1;i<=n;i++){
		for(int l=1,r=l+i-1;l<2*n;l++,r=l+i-1){ 
			for(int k=2;k<=m;k++){
				for(int h=l+k-1;h<r;h++){
					dp1[l][r][k]=max(dp1[l][r][k],dp1[l][h][k-1]*giao(sum[r]-sum[h]));
					dp2[l][r][k]=min(dp2[l][r][k],dp2[l][h][k-1]*giao(sum[r]-sum[h]));
				}
			}
		}
	}
	
	int ansmin=inf,ansmax=0;
	for(int i=1;i<=n;i++){
		ansmin=min(ansmin,dp2[i][i+n-1][m]);
		ansmax=max(ansmax,dp1[i][i+n-1][m]);
	}
	
	cout<<ansmin<<endl<<ansmax<<endl;
	return 0;
}

HDU 4632 回文子序列

题意：求出给定字符串内的不同的回文子序列的个数

题解：区间dp，但是“回文”这个性质很特殊，我们定义如下状态

$dp[l][r]:l到r区间内具有的回文子序列的个数$

接下来考虑状态转移，首先，我们可以得出

$dp[l][r]=dp[l+1][r]\cup dp[l][r-1]\\由容斥原理得\\dp[l][r]=d[l+1][r]+dp[l][r-1]-dp[l+1][r-1]$

这是所有情况都成立的，但是，如果出现了第$l$位和第$r$位的字符相同的情况的话，状态就可以增加以这两个字符为始末的回文串总数的数量，于是有如下状态转移成立

$if(s[l]==s[r])\ \ dp[l][r]=dp[l][r]+dp[l+1][r-1]+1$

PS：初始化的时候，每单个字符组成的区间的dp值为1（一个字符天然是回文的）

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int dp[2005][2005];
int main(){
	int t;
	cin>>t;
	for(int m=1;m<=t;m++){
		memset(dp,0,sizeof(dp));
		string s;
		cin>>s;
		int lens=s.length();
		for(int i=0;i<lens;i++) dp[i][i]=1;
		for(int i=2;i<=lens;i++){
			for(int j=0,ends=j+i-1;ends<lens;j++,ends=j+i-1){
				dp[j][ends]=((dp[j+1][ends]+dp[j][ends-1]-dp[j+1][ends-1])%mod+mod)%mod;
				if(s[j]==s[ends])
					dp[j][ends]=(dp[j][ends]+dp[j+1][ends-1]+1)%mod;
			}
		}
		printf("Case %d: %d\n",m,dp[0][lens-1]%mod);
	}
	return 0;
}// https://vjudge.net/problem/HDU-4632

接下来是最终挑战

洛谷 P1220 关路灯

题意：给出一排灯的位置坐标、每秒消耗功率值和你初始的位置，你每秒可以走1m，求把所有灯都关了所消耗的功率的最小值

题解：想是能想到是区间dp，但存在以下难点

难点1：状态和状态转移

我们可以想到状态如下

$dp[l][r]:关掉l到r区间内所有灯所消耗的功率值$

但这TMD怎么更新？好像缺了点什么，没错，关完这些灯你站在哪里？

只有两个选择：在$l$或在$r$，那么就好办了，状态改写为如下

$dp[l][r][0]:关掉l到r区间内所有灯后，你站在l点，所消耗的功率值\\dp[l][r][1]:关掉l到r区间内所有灯后，你站在r点，所消耗的功率值$

那么转移就好办了

$dp[l][r][0]=min(dp[l+1][r][0]+cal(),dp[l+1][r][1]+cal())\\dp[l][r][1]=min(dp[l][r-1][0]+cal(),dp[l][r-1][1]+cal())$

其中$cal()$函数是要计算的这一步的功率消耗值（可以拿前缀和搞）

难点2：遍历顺序

我们观察一下状态转移方程，l是由l+1更新过来的，因此l需要倒序遍历，相反的r需要顺序遍历，发现先遍历l比较别扭（从最长开始更新），因此考虑先遍历r，得出代码如下

#include<bits/stdc++.h>
using namespace std;
int pos[1005],power[1005];
int n,st;
int dp[55][55][3];
inline int cal(int i,int j,int l,int r){
	return (pos[r]-pos[l])*(power[i]+power[n]-power[j]);
}
int main(){
	cin>>n>>st;
	for(int i=1;i<=n;i++) cin>>pos[i]>>power[i];
	for(int i=1;i<=n;i++) power[i]=power[i-1]+power[i];
	memset(dp,0x3f3f3f,sizeof(dp));// 求最小初始化
	dp[st][st][0]=dp[st][st][1]=0;
	
	for(int j=st;j<=n;j++){ //先遍历右端点
		for(int i=j-1;i>=1;i--){ //后遍历左端点
			dp[i][j][0]=min(dp[i+1][j][0]+cal(i,j,i,i+1),dp[i+1][j][1]+cal(i,j,i,j));
			dp[i][j][1]=min(dp[i][j-1][0]+cal(i-1,j-1,i,j),dp[i][j-1][1]+cal(i-1,j-1,j-1,j));
		}
	}
	cout<<min(dp[1][n][1],dp[1][n][0])<<endl;
	return 0;
}

感想：orz，dp也太恶心了吧，毫无套路可寻，完全靠经验和智商

算法

动态规划

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

状压DP浅析上一篇

补题-2020USST算法竞赛练习场7 下一篇