区间DP

概念

区间DP的阶段一般是区间的两个端点，枚举中间分开的部分来找最优解。其阶段特征很明显，求最优值时需要预设阶段内的区间统计值。

求解方法：先初始化，然后对整个问题设最优值，枚举区间长度，枚举左端点，再枚举断点（合并点）进行转移，最后合并两边的最优值得到整个问题的最优值。有点类似分治的思想。

例题

引1. 消除回文序列

题面

给定长度为 $n$ 的序列 $a[i]$，每次可以将连续一段回文序列消去，消去后左右两边会接到一起，求最少消几次可以消完整个序列。$n≤500$。

解析

和线性模型不同，这里消去的顺序是任意的，且消完后左右会接起来。但是，不管消去的顺序是什么，每次被消去的都是一段连续的区间。

考虑消去区间 $[i,j]$，如果 $a[i]$ 和 $a[j]$ 不在一起消去，那么总有一个分界点 $k$，使得我们可以先消去 $[i,k]$ 再消去 $[k+1,j]$。

如果 $a[i]$ 和 $a[j]$ 一起消去，那么只要接在 $[i+1,j-1]$ 这段区间中最后一次消去的序列两端即可。

用 $f[i][j]$ 表示消去 $[i,j]$ 的最少次数。

$$f[i][j] = \left\{ \begin{array}{lc} \min_{i \le k < j}(f[i][k]+f[k+1][j]) & a[i] \neq a[j] \\ \min(1,f[i+1][j-1]) & a[i] = a[j] \\ \end{array} \right. $$

这样一来，这个问题有最优子问题结构且无后效性，可以利用上面的状态转移方程来进行DP。

这一类以区间长度为阶段的DP，通常被称为区间DP。

引2. 石子合并（弱化版）（洛谷P1775）

题面

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。求出将所有石子合并到一堆的最小得分。

输入：第一行为一个正整数 $N (2 \le Ｎ \le 300)$；以下 $Ｎ$ 行，每行一个正整数，小于 $10000$，分别表示第 $i$ 堆石子的个数 $(1≤i≤N)$。

输出：一个正整数表示最小得分。

解析

简单的区间DP。

$f[i][j]$ 表示将 $[i,j]$ 区间内所有石子合并的最小得分

枚举中间断点 $k$，则有 $ f[i][j]=\min_{i \le k < j} (f[i][k]+f[k+1][j])+ \sum_{k=i}^j a[k] $。

后面那项可以在预处理时求出前缀和优化掉。

时间复杂度 $O(n^3)$。

代码

# include<iostream>
# include<cstring>
using namespace std;

const int N=305;
int n,a[N],s[N];
int f[N][N];

int main(){
	cin>>n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		f[i][i]=0;
	}
	for(int l=2;l<=n;++l)
		for(int i=1;i<=n+1-l;++i){
			int j=i+l-1,t=s[j]-s[i-1];
			for(int k=i;k<j;++k)
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+t);
		}
	cout<<f[1][n]; 
	return 0;
}

A. 石子合并（洛谷P1880）

解析

实际做法和上题一样，关键是这个圈怎么处理。

法一：枚举将圈破成链的位置，然后做n次区间的石子合并，时间复杂度 $O(n^4)$，在本题的数据范围下会超时。

法二：将链延长到 $2n-1$ 个数，其中第 $i$ 位和第 $n+i$ 位完全相同，对这一整条链做一次石子合并，最后找 $f[1][n],f[2][n+1],...,f[n][2n-1]$ 的最大和最小值即可。时间复杂度 $O(n^3)$，常数为 $8$，可以通过本题。

代码

# include<iostream>
# include<cstring>
using namespace std;

const int N=205;
int n,a[N<<1],s[N<<1];
int f1[N<<1][N<<1];
int f2[N<<1][N<<1];
int ma=-1,mi=1e9;

int main(){
	cin>>n;
	memset(f1,0x3f,sizeof(f1));
	memset(f2,0xaf,sizeof(f2));
	for(int i=1;i<=n;++i){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		f1[i][i]=f2[i][i]=0;
	}
	for(int i=n+1;i<2*n;++i){
		a[i]=a[i-n];
		s[i]=s[i-1]+a[i];
		f1[i][i]=f2[i][i]=0;
	}
	for(int l=2;l<=n;++l)
		for(int i=1;i<=2*n-l;++i){
			int j=i+l-1,t=s[j]-s[i-1];
			for(int k=i;k<j;++k){
				f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+t);
				f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+t);
			}
		}
	for(int i=1;i<=n;++i){
		mi=min(mi,f1[i][i+n-1]);
		ma=max(ma,f2[i][i+n-1]);
	}
	cout<<mi<<endl<<ma;
	return 0;
}

B. 能量项链（洛谷P1063）

解析

区间DP。

状态：$f[i][j]$ 为将 $[i,j]$ 区间内所有珠子合并为一个后的最大能量。

方程：$ f[i][j]=\max_{i \le k < j}(f[i][k]+f[k+1][j]+a[i] \times a[k+1] \times a[j+1]) $。

对于环的处理和上一题一样。

时间复杂度 $O(n^3)$。

代码

# include<iostream>
# include<cstring>
using namespace std;

const int N=105;
int n,a[N<<1],ans=-1;
int f[N<<1][N<<1];

int main(){
	cin>>n;
	memset(f,0xaf,sizeof(f));
	for(int i=1;i<=n;++i){
		cin>>a[i];
		f[i][i]=f[i+n][i+n]=0;
		a[i+n]=a[i];
	}
	for(int l=2;l<=n;++l)
		for(int i=1;i<=2*n-l;++i){
			int j=i+l-1;
			for(int k=i;k<j;++k)
				f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
		}
	for(int i=1;i<=n;++i)
		ans=max(ans,f[i][i+n-1]);
	cout<<ans;
	return 0;
}

C. 凸多边形的划分

解析

乍一看这题和区间DP没啥关系，其实不然。

还是令 $f[i][j]$ 为区间 $[i,j]$ 内的点构成的凸多边形三角剖分的顶点权值乘积和的最小值，枚举和边 $(i,j)$ 构成三角形的中间点 $k$，则点 $k$ 将 $[i,j]$ 分为三个部分：三角形 $ijk$，$i$ 到 $k$ 之间的凸多边形，$k$ 到 $j$ 之间的凸多边形，所以有：

$ f[i][j]=\min(f[i][k] + f[k][j] + a[i] \times a[k] \times a[j]) $

初始值：$f[i][i]=0,f[i][i-1]=0,f[i][i+1]=0$。

本题有环，但好像并不需要处理环。

注：由于本题求乘积，数据可能超出 long long，需要使用高精度（或 __int128）。

代码

# include<iostream>
# include<cstring>
using namespace std;
# define ll __int128

const int N=55;
int n,t;
ll a[N],f[N][N];//[i,j]内的权值乘积和 

void g(ll x){
	if(!x) return;
	g(x/10);
	putchar(x%10+48);
}

void write(ll x){
	if(!x) putchar(48);
	else g(x);
}

int main(){
	cin>>n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i){
		cin>>t;
		a[i]=(ll)(t);
		f[i][i]=f[i][i+1]=(ll)(0);
	}
	for(int l=3;l<=n;++l)
		for(int i=1;i<=n-l+1;++i){
			int j=i+l-1;
			for(int k=i+1;k<j;++k)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
		}
	write(f[1][n]);
	return 0;
}

D. 括号配对

解析

比较容易想到 $f[i][j]$ 表示区间 $[i,j]$ 内未配对的括号数，难点在于状态转移方程。

本题和回文串那题不太一样，但思路上不会差太多。

考虑枚举的区间的两个端点 $i$ 和 $j$：

如果 $s[i]=s[j]$，那这对括号是匹配的，初始值 $f[i][j]=f[i+1][j-1]$；

否则，分别考虑 $[i+1,j]$ 和 $[i,j-1]$ 两个区间，找到它们中不匹配括号数的最小值，初始值 $f[i][j]=\min(f[i+1][j],f[i][j-1])+1$。

但由于最外侧的括号可能会和中间的某些括号匹配，所以我们需要枚举中间点 $k$，则 $f[i][j]=\min(f[i][j],f[i][k]+f[k+1][j])$。

注意枚举顺序。

于是最终状态转移方程为：

$$f[i][j] = \left\{ \begin{array}{lc} \min(f[i][j-1]+1,f[i+1][j]+1, \min_{i \le k <j}(f[i][k]+f[k+1][j])) & s[i] \neq s[j] \\ \min(f[i+1][j-1],\min_{i \le k <j}(f[i][k]+f[k+1][j])) & s[i] = s[j] \\ \end{array} \right. $$

代码

# include<iostream>
# include<string>
using namespace std;

const int N=105;
int n,f[N][N];//区间[i,j]内不匹配的括号数 
string s;

bool check(int x,int y){
	return s[x-1]=='('&&s[y-1]==')'||s[x-1]=='['&&s[y-1]==']';
}

int main(){
	cin>>s;
	n=s.size();
	for(int i=1;i<=n;++i)
		f[i][i]=1;
	for(int l=2;l<=n;++l)
		for(int i=1;i<=n-l+1;++i){
			int j=i+l-1;
			if(check(i,j))
				f[i][j]=f[i+1][j-1];
			else
				f[i][j]=min(f[i+1][j],f[i][j-1])+1;
			for(int k=i;k<j;++k)
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
		}
	cout<<f[1][n];
	return 0;
}

E. 分离与合体

解析

本题不仅要找最大值，还要找方案，怎么办？

可以开一个数组 $\mathit{pos}[i][j]$ 记录在 $[i][j]$ 区间分离时的位置 $k$。

状态：$f[i][j]$ 表示 $[i,j]$ 内金钥匙全部合并后的最大价值。

方程：$ f[i][j]=\max_{i≤k<j}(f[i][k]+f[k+1][j]+(a[i]+a[j]) \times a[k]) $。

初始值：$f[i][i]=a[i]$。

在每一次更新时记录 $k$，然后从 $\mathit{pos}[1][n]$ 开始递归输出。

注意枚举顺序，应该先从小到大枚举区间长度，再枚举左端点，进而计算出右端点。

代码（半成品）

# include<iostream>
using namespace std;

const int N=305;
int n,pos[N][N];
long long a[N],f[N][N],s;

void print(int l,int r){
	int k=pos[l][r];
	if(l<r){
		cout<<k<<" ";
		print(l,k);
		print(k+1,r);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		f[i][i]=a[i];
		s+=a[i];
	}
	for(int l=2;l<=n;++l)
		for(int i=1;i<=n-l+1;++i){
			int j=i+l-1;
			for(int k=i;k<j;++k)
				if(f[i][j]<f[i][k]+f[k+1][j]+(a[i]+a[j])*a[k]){
					f[i][j]=f[i][k]+f[k+1][j]+(a[i]+a[j])*a[k];
					pos[i][j]=k;
				}
		}
	cout<<f[1][n]-s<<endl;
	print(1,n);
	return 0;
}

F. 矩阵取数游戏（洛谷P1005）

解析

这题看似二维，但是每行的取数方式是完全独立的，所以是 $n$ 个一维的问题。

但是，这题取数的操作在两端，并不是中间合并的操作，应该怎么办呢？

状态：考虑 $f[i][j]$ 为剩下区间为 $(i,j)$（不包含两端）时，所取数字的最大和。

初始值：$f[0][m+1]=0$。

转移：$ f[i][i+k]=\max(f[i-1][i+k]+a[i] \times 2^{m-k},f[i][i+k+1]+a[i+k] \times 2^{m-k}) $。

本题的决策和区间长度相关，显然应该先枚举区间长度，而且本题应该倒着枚举，即区间长度从大到小来枚举。最后输出 $\sum\max_{1 \le i <m}(f[i][i+1])$ 即可。

也可以反着考虑，令 $f[i][j]$ 表示区间 $[i,j]$ 取完的最大值，它可以由 $[i+1,j]$ 取 $i$ 或者 $[i,j-1]$ 取 $j$ 得到，所以有：

$ f[i][i+k]=\max(f[i+1][i+k]+a[i] \times 2^{m-k},f[i][i+k-1]+a[i+k] \times 2^{m-k}) $

这样考虑的话最后只需要对 $f[1][m]$ 求和就可以了。

注：由于本题有 $2$ 的次幂，数据可能超出 long long，需要使用高精度（或 __int128）。

代码

# include<iostream>
using namespace std;
# define ll __int128

const int M=85;
int n,m,x;
ll p,a[M],f[M][M],ans=0;

void g(ll x){
	if(!x) return;
	g(x/10);
	putchar(x%10+'0');
}

void write(ll x,string s=""){
    if(!x) putchar('0');
    else g(x);
    cout<<s;
}

void solve(){
	p=(ll)(1)<<m;
	for(int i=1;i<=m;++i){
        cin>>x;
		a[i]=(ll)(x);
		f[i][i]=a[i]*p;
	}
	for(int l=2;l<=m;++l){
		p/=2;
		for(int i=1;i<=m-l+1;++i){
			int j=i+l-1;
			f[i][j]=max(f[i+1][j]+a[i]*p,f[i][j-1]+a[j]*p);
		}
    }
	ans+=f[1][m];
}

int main(){
	cin>>n>>m;
	while(n--) solve();
	write(ans);
	return 0;
}

延伸

洛谷P2858

作业

1. 主域
2. 洛谷 P1220 P2858 P3146 P4170 P8675

小结

区间DP问题特征：可将问题分为两两合并的形式。

方法：设最优值，枚举合并点，分解问题，再合并最优值。

步骤：设 $i$ 到 $j$ 的最优值，枚举剖分（合并）点，将 $(i,j)$ 分成左右两个区间，分别求两边最优值。

状态转移方程一般形式：$ f[i][j]=\max(f[i][k]+f[k+1][j]+\mathit{cost}(i,k,j)) $。

注意：先枚举区间长度，再枚举左端点，计算出右端点，再枚举分点。

时间复杂度 $O(n^3)$。