浅谈区间类动态规划

发表于 | 分类于 | 评论数： | 阅读次数：

区间动态规划是线性动归的拓展，在划分阶段时，往往是以区间的长度从小到大为阶段，逐步求解到到长度为N的区间的最优值

$\mathcal{Before}$ $\mathcal{Writing}$

为了加深印象，写下这则学习笔记 .

若文中有错误之处还请指出，感激不尽 .

$\mathcal{PS:}$ 菜鸡笔者水平有限，没写好不要喷我哦qwq

$\mathcal{Come}$ $\mathcal{into}$ $\mathcal{subject}$

我们先从一个问题入手。

$\mathcal{Problem Link :P1090}$

题解就是将 $n$ 堆果子任意两堆合并最终合并成一堆所需要的最小的体力耗费值。很容易想到贪心的方法，即每次合并耗费最小的两堆，可以通过维护一个小根堆实现。这里就不给出代码了，请读者自己实现。

接下来，考虑如果把题目改为每次只能合并相邻的两堆（保证果子都在一条线上，即第1堆和第 $n$ 堆不算相邻）那么很明显贪心的思路是行不通的。因此需要换一种算法。

$\mathcal{Solution}$

我们可以这么想，无论怎么合并这些果子堆，最终都是要合并成一堆的。

举个例子：假设有5堆果子（编号从1到5）需要合并，那么当她们最终合并成一堆时，一定是由 ①—②③④⑤ | ①②—③④⑤ | ①②③—④⑤ | ①②③④—⑤ 这四种合并方法中的某一种合并得到的（ $a$ — $b$ 表示 $a$ 与 $b$ 合并）。

也就是我们只需要知道最后一堆是由哪两堆合并而来的，问题也就迎刃而解了。而对于最终解需要最优，也就是合并而来的两堆也要是最优的，这就符合了动态规划最优子结构的性质，而且两堆合并的情况也是独立唯一的，不存在后效性，因此我们可以考虑用动态规划来解决这个问题。

约定：$H(a,b)$ 表示将编号从 $a$ 至 $b$ 的所有堆合并后得到的一个堆

描述状态

令 $dp[i][j]$ 表示将编号从 $i$ 至 $j$ 的所有果子堆合并能得到的最小体力耗费值（也就是 $H(i,j)$ 的最小值）。因为 $H(i,j)$ 是由 $H(i,k)$ 和 $H(k+1,j)$ 合并得到的，即上述例子中
$H(1,5)=min\begin{cases}H(1,1)+H(2,5)\\H(1,2)+H(3,5)\\H(1,3)+H(4,5)\\H(1,4)+H(5,5)\end{cases}$

由此我们可以得到状态转移方程

$dp[i][j]=min\{ dp[i][k]+dp[k+1][j] \}+cost(i,j)$ $ (1\leq i \leq j \leq n,i\leq k \leq j-1)$

所以我们去枚举 $i,j,k$ 就好了，最终的解即为 $dp[1][n]$ 。也就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
初始化 dp[i][i]=0;

for(int i=1;i<=N;++i)
  for(int j=i;j<=N;++j){
  	for(int k=i;k<=j-1;++k)
  	  dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+cost(i,j));
  	/* dp[i][j]+=cost(i,j);  状态转移方程中的 +cost(...) 操作也可以放到循环外面来做，对于此题没有影响 
  	   cost可以是一个计算花费的函数，也可以是一个数组，具体看题目而定，而在本题中表示 H(i,j) 的值，可以使用
       前缀和，即将函数cost(i,j)用来计算sum[j]-sum[i-1] 
    */
}

Res=dp[1][N];

通常 $dp$ 数组的第一维是阶段，第二维是状态。但如果你对动态规划的概念非常清楚，那么就会发现这么做其实是有问题的，因为这里的 $i$ 并不能作为阶段。

还是拿之前的例子来说，对于动态规划的最优子结构性质，我们要求当做到 $dp[1][5]$ 时，她的子问题 $dp[1][1],$ $dp[1][2]$ $…$ $dp[4][5]$ 必须都是已经确定且最优的，但放入我们写的循环里看，做到 $dp[1][5]$ 时，需要用到的 $dp[2][3]$ $,dp[2][4]…$ $dp[4][5]$ 全都还没有确定。

你也可以这么想，对于上面的状态转移方程的变量范围 $ 1\leq i \leq j \leq n , i\leq k \leq j-1 $
很明显，结合转移方程来看，$dp[k+1][j]$ 这个数组的阶段 $k+1$ 是会大于 $i$ 这个阶段的，也就是阶段 $i$ 的所有状态还没确定好，就用到了后面等待确定的阶段 $k+1$ 中的状态，这显然是错误的。

下面我们就要来考虑到底以什么来作为阶段了。

我们可以发现，对于 $H(1,5)$ ，她是由5个堆合并得到的，而她的子问题 $H(1,2),$ $H(2,4)$ 等，都是属于由2~4个的堆合并得到的，即要确定由 $n$ 个堆合并而成的 $H(a,a+n-1)$ 时，我们要做的是确定由2至 $n-1$ 个堆合并而成的 $H(a,a+k-1)$ 。因为 $k$ 一定小于 $n$ ，所以我们可以将合并的堆数作为阶段。发现合并的堆数知道了，只要知道合并操作的起始堆的位置，就能够算出终止堆的位置。

下面给出正确的伪代码

1
2
3
4
5
6
7
8
9
10
初始化 dp[i][i]=0; 

for(int L=2;L<=N;++L) //这里合并的堆数从2开始，也就是最少两个堆合并
  for(int i=1;i+L-1<=N;++i){  //枚举起点
  	int j=i+L-1;  //由起点计算出终点
  	for(int k=i;k<=j-1;++k)
  	  dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+cost(i,j));
}

Res=dp[1][N];

至此，问题已经得到解决。

$end.$

上述代码就是区间类动态规划的思想，基本套路就是1.枚举区间长度 2.枚举起点，算出终点 3.枚举过渡点 4.转移状态。

但是现在广大毒瘤出题人当然不会给你太裸的模型来做，所以他们会在一些 描述状态、转移状态、或者 在进行 $dp$ 前的处理 等方面做文章。其中环形区间动规最为经典，本文就以此为例进行分析。

我们可以对之前的题目再次进行修改：将 $n$ 堆果子围成一圈，每次只能合并相邻的两堆，其他约定与原题一致，问最少的体力耗费值。

$\mathcal{Solution}$

我们来看一张图

可以看出，环状分布解法其实就相当于从环上取一条长为 $n$ 的链，而我们做前面题目的解 $dp[1][N]$ 只是在这个环上取链的其中一种情况。

较朴素的做法就是在原先的循环最外层再套一层循环，枚举链的起点，还请读者自行尝试。这里主要介绍一种环形区间动规的经典解法。

割环

显然，既然是环，我们可以考虑在环上“切”一刀，使其变成一条链。这样由环转链，是解决环形区间动规较常用的一种方法，对于图示中的环，我们就可以将其表示为： 123451234 也就是将长度为 $n$ 的环变成了长度为 $2n-1$ 的链。那么最优解就在 12345 23451 34512 45123 51234 中。

你会发现，接下来的操作便和之前的写法完全一样了

伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
初始化 dp[i][i]=0;

for(int i=1;i<=N;++i) a[i]=a[i+N]=read();  由环转链 

for(int L=2;L<=N;++L)
  for(int i=1;i+L-1<=2*N-1;++i){
  	int j=i+L-1;
  	for(int k=i;k<=j-1;++k)
  	  dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+cost(...));
}

Res=min{dp[i][i+N-1]}  1<=i<=N

理解了之后，就可以尝试做这两道环形区间动规的经典题目。（如果还有例题可以提出来哦）

$\mathcal{Problem Link : P1880}$

$\mathcal{Problem Link : P1063}$

$end.$

我们再来看一道挺有意思的题目

$\mathcal{Description:}$

给定一个具有 $N$ 个顶点的凸多边形，将顶点从1至 $N$ 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

$\mathcal{Solution}$

约定： $P(a,b)$ 表示从点 $a$ 至 $b$ 顺时针连线组成的多边形划分三角形后能得到权值乘积和

对于题目给出的 $N$ 多边形，我们将她的顶点按顺时针方向 $1-N$ 编号。

我们可以这么想，对于最终的最优解 $P(1,N)$ ，因为此时点之间的分割线已经确定，那么我们如果割去这个 $N$ 边形外部的某一块三角形，剩下的多边形也必然是符合边数等于 $N-1$ 时的最优解的。也就是说，这符合动态规划的最优子结构的性质，并且每一种割法都是独立唯一的，不具有后效性，这也符合动态规划的原则。因此，我们可以确定了算法框架：动态规划。

令 $dp[i][j]$ 表示从点 $i$ 至 $j$ 顺时针连线组成的多边形划分三角形后能得到的最小权值乘积和（即 $P(i,j)$ 的最小值 ）。结合上图看，显然，我们要求的 $P(i,j)$ 的值就等于 $P(i,k)$ $+$ $P(k,j)$ $+$ $W(i)×W(j)×W(k)$

由此得到状态转移方程

$dp[i][j]=min\{ dp[i][k]+dp[k][j]+W(i)×W(j)×W(k) \}$ $ (1\leq i < j \leq n,i< k < j)$

于是，你会发现这又是一道区间类动态规划，接下来的做法就和前面相似了。下面是伪代码

1
2
3
4
5
6
7
8
9
10
初始化 dp[i][i+1]=0

for(register int L=2;L<=N-1;++L)
	  for(register int i=1;i+L<=N;++i){
	  	int j=i+L;
	  	for(register int k=i+1;k<=j-1;++k)
	  	  dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
	}
    
Res=dp[1][N]

另外，此题我跑了好几个oj好像都没有找到，所以我造了数据放在私人题库里了，有兴趣写一写的可以来这里qwq，由于原题数据原因需要用到高精度，顺手练练自己的高精度好啦。

这里放上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define ll long long
#define qomzi(n,i) for(register int i=1;i<=(n);++i)
#define INF 1e9
const int Maxn=160;
using namespace std;
inline int icin(){
	char c=getchar();int s=0;bool sign=0;
	while(!isdigit(c)&&c^'-')c=getchar();
	if(c=='-')c=getchar(),sign=1;
	while(isdigit(c))s=(s<<1)+(s<<3)+c-'0',c=getchar();
	return sign?-s:s;
}

int N;
struct Node{
    int len,num[Maxn<<1];
    Node(){len=1;memset(num,0,sizeof(num));}
    
    Node operator * (const Node &A)const{
    	Node ret; 
    	ret.len=A.len+len-1;
    	for(register int i=1;i<=A.len;++i)
    	  for(register int j=1;j<=len;++j)
    	    ret.num[i+j-1]+=A.num[i]*num[j],ret.num[i+j]+=ret.num[i+j-1]/10,ret.num[i+j-1]%=10;
	    while(ret.num[ret.len+1]>0)ret.len++;
	    return ret;
	}
	Node operator + (const Node &A)const{
		Node ret;
		ret.len=max(A.len,len);
		for(register int i=1;i<=ret.len;++i)
		  ret.num[i]+=A.num[i]+num[i],ret.num[i+1]+=ret.num[i]/10,ret.num[i]%=10;
		while(ret.num[ret.len+1]>0) ret.len++;
		return ret;
	}
	inline void print(){
		int f=len;
		while(!num[f]&&f>1) f--;
		for(register int i=f;i>=1;--i) printf("%d",num[i]);
	}
}dp[Maxn][Maxn],a[Maxn];
Node High(int a){
    Node ret;//cout<<a<<endl;
    while(a>0){
    	ret.num[ret.len++]=a%10;
    	a/=10;
	}
	//ret.print();cout<<'\n';
	return ret;
}
Node Min(Node x,Node y){
	int lenx=x.len,leny=y.len;
	if(lenx<leny) return x;
	if(lenx>leny) return y;
	for(register int i=lenx;i>=1;--i){
	    if(x.num[i]<y.num[i]) return x;
	      else if(x.num[i]>y.num[i]) return y;	
	}
	return x;
}

inline void init(){
	N=icin();
	for(register int i=0;i<=N;++i)
	  for(register int j=0;j<=N;++j)
	    dp[i][j].len=250,dp[i][j].num[250]=9;
	qomzi(N,i) a[i]=High(icin()),dp[i][i+1].len=dp[i][i+1].num[250]=0;
}
int main(){
	init();
	for(register int L=2;L<=N-1;++L)
	  for(register int i=1;i+L<=N;++i){
	  	int j=i+L;
	  	for(register int k=i+1;k<=j-1;++k)
	  	  dp[i][j]=Min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
	}
	dp[1][N].print();
    return 0;
}

$end.$

$\mathcal{After}$ $\mathcal{Writing}$

经过分析了几道区间类动态规划的题目，相信你一定有所领悟了吧，尽管此类dp或许会有大致的框架，但在解题时还是不能死板盲目地想当然放上模板做法，因为针对不同的题目代码内容还是会有微小的变化的。所以在做题目时，我们要将所给的问题一层一层地剥开，最后找到问题的实质，这样，面对动态规划的题目就可以得心应手啦。

这里放上网上的一位博主对区间类型dp的理解

“区间动态规划是线性动归的拓展，在划分阶段时，往往是以区间的长度从小到大为阶段，逐步求解到到长度为N的区间的最优值，在枚举每一个区间的最优值时，由于当前区间内又有很多种合并方式并到到当前区间，那么就需要枚举这些合并方式中产生的值维护最优值，合并的不同，可以看作是区间划分的不同，划分时需要枚举划分的位置，即分割点。 那么对于区间类动态规划问题，往往可以将问题分解成为两两合并的形式。其解决方法是对整个问题设最优解，枚举分割点，维护最优值。

现在再看这段话就一定会觉得很有感触了吧qwq

最后，如果你认真看了这篇文章，或多或少一定会有点收获叭（dalao请忽略qwq）。如果你还有什么问题请发在讨论区或者私信我，我会不定时解疑的。

另外笔者文化课水平欠佳，有些抽象的意思实在不能解释的很清楚，还请你们自行画图列表帮助理解哦。

${End.}$