文章目录
一、前言
??区间DP又名区间动态规划,在 LeetCode 上属于难度中上的题,而 ACM 竞赛中属于简单级别,为必须掌握的内容。实际思想也比较简单,基本上看完我写的总结,大部分题目都可以用模板套出来了。
??区间DP的状态设计相对简单,基本大部分问题都是用 f [ i ] [ j ] f[i][j] f[i][j] 代表区间 [ i , j ] [i,j] [i,j] 上的最优解。难点在于状态转移的设计上。本文将通过一些例题,详细讲解常见的状态转移套路。
??对于区间DP来说,一个最经典的思想就是正难则反,听我娓娓道来。
二、石子归并
- 石子归并问题,基本上是所有讲解 区间 DP 的文章都会提到的一个题,那么我也不例外。
【例题1】有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 堆石子摆放成一排,第 i i i 堆的重量为 w i w_i wi?,现要将石子有次序地合并成一堆。规定每次只能选相邻的二堆合并成新的一堆,合并的消耗为当前合并石子的总重量。试设计出一个算法,计算出将 n n n 堆石子合并成一堆的最小消耗。
- 在思考用动态规划求解的时候,我们可以先想想如果穷举所有方案,会是什么情况。
1、穷举
- 对于这个问题来说,我们第一个决策可以选择一对相邻石子进行合并,总共有 n ? 1 n-1 n?1 种情况;对于 5堆 石子的情况,第 1 次合并总共有 4 种选择:
- 1)选择 第 1 堆 和 第 2 堆 的石子进行合并,如图二-1-1所示:
图二-1-1 - 2)选择 第 2 堆 和 第 3 堆 的石子进行合并,如图二-1-2所示:
图二-1-2 - 3)选择 第 3 堆 和 第 4 堆 的石子进行合并,如图二-1-3所示:
图二-1-3 - 4)选择 第 4 堆 和 第 5 堆 的石子进行合并,如图二-1-4所示:
图二-1-4 - 以上任意一种情况都会把石子变成 4 堆,然后就变成了求解 4 4 4 堆石子的问题;我们可以采用同样方法,把石子变成 3 3 3 堆, 2 2 2 堆,最后变成 1 1 1 堆,从而求出问题的最终解。
- 当然,这是一个递归的过程,每次合并可以将石子堆数减一,总共进行 n ? 1 n-1 n?1 次合并,每个阶段可行的方案数都是乘法的关系,穷举的方案总数就是 ( n ? 1 ) ! (n-1)! (n?1)!;
- 例如,上面提到的剩下的这 4 堆石子,采用深度优先搜索枚举所有可行解的搜索树如图二-1-5所示:
图二-1-5 - 图中用 ‘-’ 表示不同堆石子之间的分隔符,即 1-2-3-4 代表 4 堆的情况,12-3-4表示 第 1 堆 和第 2 堆 合并后的情况。
- 对这么多种方案取总消耗最小的,正确性是一定可以保证的,因为我们枚举了所有情况,然而时间上肯定是无法接受的。
- 那么,如何来优化搜索呢?
- 我们发现这个问题的难点在于:当选出的两堆石子合并以后,它的重量变成了合并后的和,对于 n n n 堆石子,选择的 n ? 1 n-1 n?1 种合并方式,到达的都是不同的状态,无法进行状态存储。
2、正难则反
- 当没有头绪的时候,我们试着将问题反过来思考;
- 我们发现这棵深度优先搜索树的所有叶子结点都是一样的,这就为我们解决问题带来了突破口;
- 对于 [ 1 , n ] [1, n] [1,n] 堆石子,假设已经合并了 n ? 2 n-2 n?2 次,必然只剩下 二堆石子,那么我们只需要合并最后一次,就可以把两堆石子变成一堆,假设合并最后一次的位置发生在 k k k,也就是最后剩下两堆分别为: [ 1 , k ] [1, k] [1,k] 和 [ k + 1 , n ] [k+1, n] [k+1,n],如图二-2-1所示:
- 注意,这个时候 [ 1 , k ] [1, k] [1,k] 和 [ k + 1 , n ] [k+1, n] [k+1,n] 已经各自合并成一堆了,所以我们把问题转换成了求 [ 1 , k ] [1, k] [1,k] 合并一堆的最小消耗,以及 [ k + 1 , n ] [k+1, n] [k+1,n] 合并成一堆的最小消耗;而这里 k k k 的取值范围为 [ 1 , n ? 1 ] [1, n-1] [1,n?1];
- 利用这样的方法,逐步将区间缩小成 1,就可以得到整个问题的解了。
3、设计状态
- 令 f [ i ] [ j ] f[i][j] f[i][j] 表示从 第 i i i 堆 石子到 第 j j j 堆 石子合并成一堆所花费的最小代价。
4、状态转移方程
- f [ i ] [ j ] = { 0 i = j min ? k = i j ? 1 ( f [ i ] [ k ] + f [ k + 1 ] [ j ] + c o s t ( i , j ) ) i ≠ j f[i][j] = \begin{cases} 0 & i=j\\ \min_{k=i}^{j-1}(f[i][k] + f[k+1][j] + cost(i,j)) & i \neq j\end{cases} f[i][j]={0mink=ij?1?(f[i][k]+f[k+1][j]+cost(i,j))?i=ji?=j?
- 其中 c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=∑k=ij?wk?
- 有了上面 “正难则反” 的解释,这个状态转移方程就很好理解了;
- 1)当 i = j i=j i=j 时,由于 f [ i ] [ j ] f[i][j] f[i][j] 已经是一堆了,所以消耗自然就是 0 了;
- 2)当 i ≠ j i \neq j i?=j 时,我们需要把目前剩下的两堆合并成一堆,一堆是 f [ i ] [ k ] f[i][k] f[i][k] ,另一堆是 f [ k + 1 ] [ j ] f[k+1][j] f[k+1][j],这两堆合并的消耗就是 从 第 i i i 堆到第 j j j 堆的重量之和,即 c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=∑k=ij?wk?,而对于合并方案,总共 k = j ? i k=j-i k=j?i 种选择,所以枚举 j ? i j-i j?i 次,取其中最小值就是答案了。
- 通过记忆化搜索求解 f [ 1 ] [ n ] f[1][n] f[1][n] 就是最后的答案。
- 以上就是最经典的区间 DP 问题。
三、区间DP的特征
1、状态设计
- 利用区间来描述状态,所以一般情况下都可以用 f [ i ] [ j ] f[i][j] f[i][j] 作为 DP 数组,其中 i , j i, j i,j 为问题对应的区间 [ i , j ] [i, j] [i,j] 的左右端点;
- 当然,有的时候需要一个辅助维,状态可能会设计成 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] ,其中 i , j i, j i,j 为问题对应的区间 [ i , j ] [i, j] [i,j] 的左右端点,而 k k k 因题而已,这个在下文 区间DP的进阶 这一节里会讲到。
2、状态转移
- 状态转移一定是从 区间长度短 的状态 到 区间长度长 的状态;
3、时间复杂度
- 涉及到利用 区间DP 来求解的问题,一般都有一个对应的序列:
- 1)当序列的长度为 n ≤ 300 n \le 300 n≤300 时,区间DP 的时间复杂度一般为 O ( n 3 ) O(n^3) O(n3),其中 状态转移时间复杂度 为 O ( n ) O(n) O(n);
- 2)当序列的长度为 n ≤ 1000 n \le 1000 n≤1000 时,区间DP 的时间复杂度一般为 O ( n 2 ) O(n^2) O(n2),其中 状态转移时间复杂度 为 O ( 1 ) O(1) O(1);
四、区间DP的求解
- 接下来我们再通过一道例题来完整了解下 区间DP 的求解过程,并且尝试用 递归 和 迭代 两种方法来实现它。
【例题2】给定一个 n ( 3 ≤ n ≤ 100 ) n(3 \le n \le 100) n(3≤n≤100) 个元素的序列 a i a_i ai?,每删除一个元素,就会产生一定的消耗,消耗为它本身与相邻两数的乘积,首尾两个数不能删除,问将数字删除到只剩两个,最小的总消耗是多少。
1、思路分析
- 和石子归并的思路一样,如果采用暴力枚举删除的思路,利用深度优先搜索遍历所有情况,得到的搜索树,第一层有
n
?
2
n-2
n?2 种选择,第二层有
n
?
3
n-3
n?3 种选择,最后一层有一种选择,整个算法的时间复杂度为
O
(
n
!
)
O(n!)
O(n!),当
n
=
5
n=5
n=5 的搜索树如下图所示(其中数字代表下标):
图四-1-1 - 可以发现有很多重复的计算,比如 [125]、[135]、[145] 都被计算了两次;
图四-1-2 - 搜索和动态规划的区别就是动态规划能够把一些子问题计算出来以后存起来,下次要用到的时候直接返回,无需重复计算。
- 对于一个序列,最后一定会经过
n
?
2
n-2
n?2 次删除数字变成只剩下首尾两个数的情况,即:
- 那么根据 “正难则反” 的思想,我们不去考虑第一个删除的数,而是考虑最后一个被删除的数的情况;
- 令最后一个被删除的数是
a
k
a_k
ak?,情况如下:
图四-1-4 - 也就是说,如果最后一个被删除的是 a k a_k ak?,那么消耗就是 a 1 a k a n a_1 a_k a_n a1?ak?an?,那么对于 [ 1... k ] [1 ... k] [1...k] 和 [ k . . . n ] [k ... n] [k...n] 这两个区间,前者需要删除 k ? 2 k-2 k?2 个数,后者需要删除 n ? k ? 1 n-k-1 n?k?1 个数,并且两个端点的数是不能被删除的。
- 这样就把原本大区间的问题,转换成了两个小区间的问题。
- 令 f [ i ] [ j ] f[i][j] f[i][j] 表示区间 [ i , j ] [i, j] [i,j] 中的数删除除端点外的所有数得到的最小消耗,则有状态转移方程如下:
- f [ i ] [ j ] = { 0 j ? i ≤ 1 min ? k = i + 1 j ? 1 ( f [ i ] [ k ] + f [ k ] [ j ] + a i a k a j ) j ? i > 1 f[i][j] = \begin{cases}0 & j-i \le 1\\ \min_{k=i+1}^{j-1}(f[i][k] + f[k][j] + a_i a_k a_j) & j-i \gt 1\end{cases} f[i][j]={0mink=i+1j?1?(f[i][k]+f[k][j]+ai?ak?aj?)?j?i≤1j?i>1?
- f [ 1 ] [ n ] f[1][n] f[1][n] 即为最后的答案。
2、代码实现
1)递归实现
- 比较直观的求解 区间DP 的方法是记忆化搜索,只要想好递归出口 和 状态转移,基本就是套模板了。
int dfs(int l, int r) {
if(l + 1 == r) {
return 0; // 1)
}
int &val = f[l][r];
if(val != inf) { // 2)
return val;
}
val = 1e9;
for(int k = l + 1; k < r; ++k) {
int v = dfs(l, k) + dfs(k, r) + a[l] * a[k] * a[r];
val = min(val, v); // 3)
}
return val;
}
- 1)当区间长度为 2 的时候,无需进行删除,已经到达递归出口,所以消耗为 0;
- 2)初始化所有区间状态值为 f [ l ] [ r ] = i n f f[l][r] = inf f[l][r]=inf,如果不等于这个值,说明已经计算出来了,则无需递归计算,直接返回已经计算出来的值即可;
- 3)利用子区间计算出来的值,进行状态转移;
- 关于记忆化搜索相关的内容,如果还有疑问,可以参考我之前写的一篇文章:
2)迭代实现
- 当然也有迭代的方式来实现的,迭代求解需要注意状态转移的方向,之前已经说过,状态转移一定是从小区间往大区间进行转移的,所以小区间的最优值需要先被计算出来。
- 于是我们可以按照区间的长度进行枚举,对于二维的状态,前两层枚举分别为 区间长度 和 区间左端点。我们来看看迭代版本的实现。
for (int len = 1; len <= n; ++len) {
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1; // 1)
if (len == 1 || len == 2) {
f[l][r] = 0; // 2)
continue;
}
f[l][r] = 1e9;
for (int k = l + 1; k < r; ++k) {
int v = f[l][k] + f[k][r] + a[l] * a[k] * a[r];
f[l][r] = min(f[l][r], v); // 3)
}
}
}
- 1)优先枚举区间长度 l e n len len,再枚举左端点 l l l,这样区间右端点就可以通过两者计算出来: r = l + l e n ? 1 r = l + len - 1 r=l+len?1,并且保证了状态转移的方向一定是从小区间到大区间;
- 2)这一步对应的是递归实现的递归出口部分;
- 3)这一步对应的是状态转移的部分;
- 如图四-2-1的动图,展示的是迭代求解的顺序,灰色的格子代表无效状态,红色的格子代表为长度为 2 的区间,橙色的格子代表为长度为 3 的区间,金黄色的格子则代表长度为 4 的区间,黄色的格子代表我们最终要求的区间状态,即
f
[
1
]
[
5
]
f[1][5]
f[1][5]。
图四-2-1
五、区间DP的进阶
1、环形区间
【例题3】有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 堆石子摆放成一圈,第 i i i 堆的重量为 w i w_i wi?,现要将石子有次序地合并成一堆。规定每次只能选相邻的二堆合并成新的一堆,合并的消耗为当前合并石子的总重量。试设计出一个算法,计算出将 n n n 堆石子合并成一堆的最小消耗。
- 这个问题和 【例题1】 的区别在于原本的链状结构变成了环状结构,我们可以将石子拷贝一份同样的数据,即令 w n + i = w i w_{n+i} = w_i wn+i?=wi?,将原来的长度为 n n n 的序列变成 2 n 2n 2n,然后枚举左端点 l ∈ [ 1 , n ] l \in [1,n] l∈[1,n],做 n n n 次区间 DP,然后再取最小值,时间复杂度 O ( n 4 ) O(n^4) O(n4)。
- 注意到这里计算 [ l , l + n ] [l, l+n] [l,l+n] 和 [ l + 1 , l + 1 + n ] [l+1, l+1+n] [l+1,l+1+n] 区间DP 的最优值时, [ l + 1 , l + n ] [l+1, l+n] [l+1,l+n] 这段区间是两者的重叠区间,所以这里同样是可以记忆化的,即可以把 n n n 次 区间DP 放在一起做(即只需要一次初始化),然后求:
- min ? ( f [ 1 ] [ n ] , f [ 2 ] [ 1 + n ] , . . . , f [ n ] [ 2 n ? 1 ] ) \min( f[1][n], f[2][1+n], ..., f[n][2n-1]) min(f[1][n],f[2][1+n],...,f[n][2n?1])
- 就是最后的答案了,这时候,时间复杂度是 O ( n 3 ) O(n^3) O(n3) 的。
2、回文子序列
【例题4】给定一个 n ( n ≤ 1000 ) n( n \le 1000) n(n≤1000) 个元素 a i a_i ai? 的序列,求它的最长的回文子序列的长度。
- 令 f [ i ] [ j ] f[i][j] f[i][j] 为第 i i i 个元素到第 j j j 个元素的最长回文子序列的长度,考虑以下几个情况:
- 1) i > j i \gt j i>j:这个时候代表它是个空串,所以最长回文子序列的长度肯定为 0;
- 2) i = j i=j i=j:对于长度为 1 的串,本身就是一个回文序列,所以最长回文子序列的长度为 1;
- 3) i < j , a i ≠ a j i < j,a_i \neq a_j i<j,ai??=aj?:由于区间端点的两个元素值不相等,所以 f [ i ] [ j ] f[i][j] f[i][j] 不可能比 f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j] 或者 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1] 更长,至多和两者的大者相等,即 f [ i ] [ j ] = max ? ( f [ i + 1 ] [ j ] , f [ i ] [ j ? 1 ] ) f[i][j] = \max(f[i+1][j], f[i][j-1]) f[i][j]=max(f[i+1][j],f[i][j?1]),这样就把区间缩小了;
- 4) i < j , a i = a j i < j,a_i = a_j i<j,ai?=aj?:由于区间端点的两个元素值相等,所以只需要知道这两个元素包围的区间的最大值,即 f [ i + 1 ] [ j ? 1 ] f[i+1][j-1] f[i+1][j?1],再加上 2 就是包含两端点的最长回文子序列的长度;那么当然还要考虑不包含的情况,也就是(3)的情况;
- 于是,可以得出状态转移方程如下:
- f [ i ] [ j ] = { 0 i > j 1 i = j max ? ( f [ i + 1 ] [ j ] , f [ i ] [ j ? 1 ] ) i < j , a i ≠ a j max ? { f [ i + 1 ] [ j ? 1 ] + 2 f [ i + 1 ] [ j ] f [ i ] [ j ? 1 ] i < j , a i = a j f[i][j] = \begin{cases}0 & i > j \\ 1 & i=j \\ \max(f[i+1][j], f[i][j-1]) & i < j, a_i \neq a_j \\ \max \begin{cases} f[i+1][j-1] + 2 \\ f[i+1][j] \\ f[i][j-1] \end{cases} & i < j, a_i = a_j\end{cases} f[i][j]=????????????????????01max(f[i+1][j],f[i][j?1])max??????f[i+1][j?1]+2f[i+1][j]f[i][j?1]??i>ji=ji<j,ai??=aj?i<j,ai?=aj??
3、辅助维
- 当单纯区间无法表示状态时,我们就需要增加辅助维来解决这个问题,下面的这道例题较难,属于竞赛难度,如果单纯是为了面试而学的算法,可以略过此题。
【例题5】(较难) n ( n ≤ 200 ) n ( n \le 200 ) n(n≤200) 个方块排成一排,每个方块一种颜色,每次可以选择其中一种连续的颜色块进行消除,消除的分数为色块长度的平方,求最后全部色块消除的总分,要求这个最大值;
如上图所示,输入:
9
1 2 2 2 2 3 3 3 1
输出: 29 ( 4 2 + 3 2 + 2 2 ) 29 (4^2+3^2+2^2) 29(42+32+22)
- 首先对于这个问题,本身已经连在一起的方块一定是一起消除的,所以首先一定要预处理输入,将相同颜色的方块归并, c o l o r i color_i colori? 表示第 i i i 种方块的颜色, n u m i num_i numi? 表示第 i i i 种方块的数量;
- 那么如果用 f [ i ] [ j ] f[i][j] f[i][j] 来表示区间 [ i , j ] [i, j] [i,j] 下能够消除得到的最大分数,我们发现无法进行状态转移,因为如果 i i i 和 j j j 能够放在一起消除的条件是 [ i + 1 , j ? 1 ] [i+1, j-1] [i+1,j?1] 的区间上都已经被消除,但是从这个状态表示上并不能体现,所以,我们需要增加一维来表示状态。
- 令 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示 [ i , j ] [i, j] [i,j] 消除,并且第 j j j 个块连同后面 k k k 个颜色相同块消去的最大分数;
- 1)第 j j j 个块单独和后面的 k k k 个块消掉,那么分数为 f [ i ] [ j ? 1 ] [ 0 ] + ( n u m j + k ) 2 f[i][j-1][0] + (num_j+k)^2 f[i][j?1][0]+(numj?+k)2 ;
- 2)对于 s ∈ [ i , j ) s \in [i, j) s∈[i,j),如果 c o l o r s = c o l o r j color_s = color_j colors?=colorj?,那么如果我们要把他们在后续归并到一起,势必中间的 ( s , j ) (s, j) (s,j) 这些块要单独计算,其最大值为 f [ s + 1 ] [ j ? 1 ] [ 0 ] f[s+1][j-1][0] f[s+1][j?1][0];并且,为 [ i , s ] [i,s] [i,s] 这个区间的最后一种类型的块,增加了 n u m j num_j numj? 个,即最大值为 f [ i ] [ s ] [ n u m j + k ] f[i][s][ num_j+k ] f[i][s][numj?+k],则有:
- f [ i ] [ s ] [ n u m j + k ] + f [ s + 1 ] [ j ? 1 ] [ 0 ] f[i][s][ num_j + k ] + f[s+1][j-1][0] f[i][s][numj?+k]+f[s+1][j?1][0]
- 联合(1) 和 (2)得出状态转移方程:
- f [ i ] [ j ] = max ? { f [ i ] [ j ? 1 ] [ 0 ] + ( n u m j + k ) 2 f [ i ] [ s ] [ n u m j + k ] + f [ s + 1 ] [ j ? 1 ] [ 0 ] c o l o r s = c o l o r j f[i][j] = \max \begin{cases} f[i][j-1][0] + (num_j+k)^2 \\ f[i][s][ num_j + k ] + f[s+1][j-1][0] & color_s = color_j\end{cases} f[i][j]=max{f[i][j?1][0]+(numj?+k)2f[i][s][numj?+k]+f[s+1][j?1][0]?colors?=colorj??
六、区间DP的常规思路
1、切割 / 合并区间
- 将大区间无脑切割成两个子区间,分别计算两个子区间的最优值,再通过两个子区间的最优值,计算整个大区间的最优值。
2、last 原则
- 永远不去想第一步要干什么,而是想最后一步是要干什么,然后再去枚举最后一步的所有情况,从而缩小区间。
3、添加辅助维
- 有时候二维的区间无法表示状态,或者无法进行状态转移的时候,我们可以尝试再增加一个纬度,然后再去想状态转移方程。
- 关于 区间 DP 的内容到这里就全部结束了,如果还有不懂的问题可以留言告诉作者或者添加作者的微信公众号。
- 本文所有示例代码均可在以下 github 上找到:github.com/WhereIsHeroFrom/Code_Templates
七、区间DP相关题集整理
题目链接 | 难度 | 解法 |
---|---|---|
PKU 1651 Multiplication Puzzle | ★☆☆☆☆ | 【例题2】石子归并 |
洛谷 P1880 石子合并 | ★☆☆☆☆ | 【例题3】石子归并 + 环形处理 |
HDU 5115 Dire Wolf | ★★☆☆☆ | 石子归并 |
PKU 1179 Polygon | ★★☆☆☆ | 石子归并 + 环形处理 |
PKU 2955 Brackets | ★★☆☆☆ | 括号匹配 |
PKU 1141 Brackets Sequence | ★★☆☆☆ | 括号匹配 + 路径输出 |
PKU 3186 Treats for the Cows | ★★☆☆☆ | 区间DP / 两种决策 |
PKU 3042 Grazing on the Run | ★★☆☆☆ | 区间DP / 两种决策 |
HDU 4632 Palindrome subsequence | ★★☆☆☆ | 回文序列 / 计数DP |
HDU 4521 吉哥系列故事——完美队形I | ★★☆☆☆ | 区间DP / 回文序列 |
HDU 2476 String painter | ★★☆☆☆ | 区间DP / 瞎搞搞 |
HDU 4283 You Are the One | ★★★☆☆ | 区间DP + 前缀和 |
HDU 5396 Expression | ★★★☆☆ | 石子归并 + 排列组合 |
HDU 5151 Sit sit sit | ★★★☆☆ | 区间DP + 排列组合 |
HDU 6365 Shoot Game | ★★★☆☆ | 区间DP + 计算几何 |
HDU 4745 Two Rabbits | ★★★☆☆ | 【例题4】区间DP + 环形处理 |
HDU 5693 D Game | ★★★☆☆ | 消消乐 + 二分查找 |
HDU 5900 QSC and Master | ★★★☆☆ | 消消乐 + gcd |
PKU 2176 Folding | ★★★★☆ | 区间DP + 路径回溯 |
PKU 1390 Blocks | ★★★★☆ | 【例题5】消消乐 + 辅助维 |
HDU 3427 Clickomania | ★★★★☆ | 消消乐 + 辅助维 |
HDU 4293 Groups | ★★★★☆ | 区间DP + 思维 |
PKU 2168 Joke with Turtles | ★★★★☆ | 区间DP + 思维 |