区间DP解析超详细版！！街边老奶奶也喜欢看的好博客_区间dp详解

区间DP解析超详细版！！

---

在上章 背包 （<—点击传送）中我们讲到DP是一种记忆化搜索，需要状态的传递来达到更深层次的搜索。

价值与代价的组合嵌套成背包中状态，而区间DP，则是需要子区间的更迭，环环相扣由子区间之间的组合来组成父区间的值，通过级级解决区间的合并问题来得出最优值。

1. 概念入门

---

第一次接触区间DP是在和学长闲聊时被考到的

当时的问题是：
在一个环形操场上放着若干堆石子，定义代价是相邻两堆石子合并时的重量和，求合成一堆时的最小代价。

当时第一反应是用孤儿贪心思想。众所周知，贪心是保证当前抉择最优却无法保证整体策略最优。

2. 线性石子归并

---

此题不适合入门学者，修改一下，线性石子归并（<—点击传送）

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

给一个 5 堆的样例：8 4 6 3 5

运用贪心（每次合并最小代价和的两堆），算出结果62，最优解是60

放弃贪心我们来学习区间DP吧！

规定：Q( a , b )代表从第 a 堆到第 b 堆的区间内合并的最小代价值。

用逆推思想，假设自己是上帝，知道如何组合去做到最优解：合并的最后一定是两堆相合，设为 堆a 和 堆b，知晓最优的 a,b 就可以推出答案； 那么 堆a/堆b 也是两堆所和，设为 堆c和堆d/堆e和堆f，知晓…

发现问题开始递成一个个子问题，和DP思想逐渐吻合。

并且分区到最底层一定是 Q( n , n ), 即某一堆的石子量，是我们已知的条件。

大区间包含小区间，我们解决了小区间才能解决大区间。我们 跑遍一个区间的所有可能组合 ，

例如：Q( 1 , 5 ) = min { Q(1,1)+Q(2,5), Q(1,2)+Q(3,5), Q(1,3)+Q(4,5), Q(1,4)+Q(5,5) }

就可以取出这个区间的最优组合，知晓这个区间的最优解。

在 for 循环中的最外层放置L（length）,使得小区间会在大区间之前被处理完

区间左端为 i ，右端为 j = i + L -1 ，在之间放一个中间商 k 赚差价

那么给出状态转移方程：Q ( i , j ) = min { Q( i , k ) + Q ( k + 1 , j ) } + cost( i , j )------------( 1 <= i <= k <= j <= N )

for 循环注意 k 的存在范围，别出错越界

//预处理
fill( DP[0][0] ,DP[0][0]+(N+1)*(N+1) , 99999999);
for( int i=1 ; i <= N ; ++i )
	DP[i][i]=arr[i];  //arr[i]代表第 i 堆石头的石子数
cost[0]=0;
for( int i=1 ; i <= N ;++i )
	cost[i]=cost[i-1]+arr[i]; //创建前缀和数组cost[]
//核心代码
for( int L = 2 ; L <= N ; ++L )
	for( int i = 1 ; i < N ; ++i )
		for( int k = i ; k < i+L-1 ; ++k )
			DP[i][i+L-1] = min(DP[i][k]+DP[k+1][i+L-1]+cost[i,j];//cost[i,j]=cost[j]-cost[i-1]
1
2
3
4
5
6
7
8
9
10
11
12

术语普及–L（区间长度） ，i（起点）， j（终点），k（过渡点）

3. 环形石子归并

---

我们再来看看 环形石子归并（<—点击传送）

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分，计算出将N堆石子合并成1堆的最小得分和最大得分.

环形区间的关键点就是 割环

借用 图论 的眼光，每堆是一个点，每相邻的点之间有一条路径，一个路径走一次。那么，n个点，n个路径。

合并一次少一个点，少一个路径。合并的最后，剩一堆，也就是一个点，相对应的，也剩一个路径。根据路径使用一次便消失的规定，此路径从未使用过。也就是说，这条路径最初时连接的两点一直没有通过此路径合并。

诶诶诶～那么我们是不是可以去掉这个路径？

反正没用过，在与不在一个样。去掉也无伤大雅，同时也实现了割环，成了线性。

线性我们就可以使用之前的方法解题。

那么现在我们真正的的问题来了。我贴喵怎么知道究竟是哪一条边无用呢？

我们需要在 n 条中找一条可有可无边 ----^等价于----> 在 n 中找 n-1 条有用的边

给个样本：1 8 1 2 3 8

我们需要在 181238，812381，123818，238181，381812，818123中找到最优的，无脑点，线性算法各跑1次，全部算出。

再观察一下，相邻的两组数据，有n-1位是相同的，那就共用一下呗

我们创建一列：18123818123

此列中任意长度为 n 的数据链对应上面某一系列

这，就是优化！！！

给出核心代码（求最小值函数）

int minn(){
    for(int len=2;len<=n;++len){
        for(int i=1;i+len-1<n*2;++i){
            int j=i+len-1;
            for(int k=i;k<j;++k){
                int a=DP_MIN[i][j],b=DP_MIN[i][k],c=DP_MIN[k+1][j],d=sum[j]-sum[i-1];
                if(a>b+c+d)
                    DP_MIN[i][j]=DP_MIN[i][k]+DP_MIN[k+1][j]+sum[j]-sum[i-1];
            }
        }
    }
    int ans=inf;
    for(int i=1;i<=n;++i){
        ans=min(DP_MIN[i][i+n-1],ans);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 奇怪的题题目目

---

再来看一题长得奇怪怪的区间DP题

Halloween Costumes（<—点击传送）

题目：

小灰灰参加圣诞节的一些派对，并且需要穿上对应派对的衣服，所以他需要多次换衣服，为了方便，他可以选择脱掉一些衣服或者穿上新衣服，比如说，他穿着超人的衣服，外面又穿着死侍的衣服，当他要参加超人服装派对时，他可以选择脱掉死侍的衣服（因为死侍衣服的里面有超人的衣服），或者他可以在穿一件超人的衣服，小灰灰是个爱干净的人，当他脱下死侍的衣服后，如果需要再穿死侍的衣服，他会选择再穿一件新的。（如果他先穿A衣服，又穿上B衣服，再穿一件C衣服，如果他想让最外面的衣服是A，他可以选择直接穿一件A，或者先把C脱掉，再把B脱掉）。

采用第二个样例

1 2 1 1 3 2 1

进行分析，用第 i 个派对为 x 轴，衣服的层数为 y 轴，建立样本分析表：

答案数量就是曲线上升段数（最少），表格所示是最优方案之一

那么要让上升段数最少，下降段数和平段数就要尽可能多

在算法区间合并时，设前头区间为 a=[ a1 , a2 ] ，后头区间为 b = [ b1 , b2 ]

在枚举中间量时，a2 为 k ，a1 为 i ，b2 为 j

如图，两个区间我们最多利用 双头双尾 4个位置

a头b头 ，a头b尾 ，a尾b头 ，a尾b尾 四种合并情况

a 头和 b 头相同，就可以让区间 a 的衣服脱掉，脱到 a ，就可以少穿一件衣服---->区间 [ a1 , b2 ] = num( a ) + num( b ) - 1 ;

a 尾和 b 头相同，就可以从 a 尾直接过渡到 b 头 ，就可以少穿一件衣服---->区间 [ a1 , b2 ] = num( a ) + num( b ) - 1 ;

在枚举区间合并时其实只要判断这一种情况就足够了

1. 区间DP会枚举所有区间组合情况，四种中三种情况合并情况实际上是等价的_{（敲一敲黑板，划重点～}

2. ^{比较孤儿的} a尾b头 模式是两对象设定只能距离差一，其他的跨度都可大可小。所以其余三种任一可独当一面，但 a尾b头 有局限性不能单枪匹马出战，可被其余任一包含

给出核心代码

for(int l=2;l<=num;++l){

            for(int i=1;i<=num-l+1;++i){

                for(int k=i;k<i+l-1;++k){

                    if(/*line[k]==line[i+l-1]||*//*line[i]==line[i+l-1]*/line[k+1]==line[i])
                        dp[i][i+l-1]=fmin(dp[i][i+l-1],dp[i][k]+dp[k+1][i+l-1]-1);
                    else
                        dp[i][i+l-1]=fmin(dp[i][i+l-1],dp[i][k]+dp[k+1][i+l-1]);
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 区间DP的优化

---

区间DP还有优化，没想到吧(￣▽￣)~*

四边形不等式优化，看不看得懂，挺随缘的_[笑哭]

当初我看了三四天才看懂，不过没怎么用现在都快忘记惹，分享一下我当时看的感觉比较好的博客：

区间dp之四边形不等式优化详解及证明_萧魂不散_{个人比较喜欢这位大佬的排版风格[手动狗头]}

【教程】四边形不等式学习笔记_mlystdcall

四边形不等式优化讲解（详解）_NOIAu

以后再写这个证明了～

附录

再推荐一篇区间入门好博客

浅谈区间类动态规划_Koakuma