算法专题——区间型动态规划


最近复习动态规划,写几篇博客进行总结

区间型DP特点

? 区间型DP中的区间通常指的就是字面意义上的区间,以一组数列为例,那么[i][j]表示的就是i到j的这个区间。

? 区间型动态规划的递归关系,通常是呈现出去头去尾的特点,以下面的伪代码为例。

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) //区间[i][j]由去掉头(或者去掉尾)的[i + 1][j](dp[i][j - 1])推出

? 基于此种特性,区间型DP的代码实现通常要对区间长度进行循环,即从区间长度短的循环到区间长度长的,当求当前状态的值的时由于使用到的子状态的区间长度都小于当前状态,因此都可以推出,非常的合理且符合直觉,见下面伪代码。

for (int i = 1; i <= len; i++) 			//循环区间长度
	for (int j = 0; j <= n - len; j++) 	//循环做端点
		for (int z = j + 1; z < n; z++)	//循环右端点
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); //转移方程

例题



石子合并


题面:


分析:

? 对于成圈的东西,可以给它复制一个贴后边,就可以变成普通的成串的序列。问题就变成了长度为2 * n的序列里,找出长度为n的连续子序列,进行合并之后使得该序列满足题意。

? 不难发现(,我们可以使用dp[i][j]表示区间i到区间j可以经过合并后得到的最大分数,接着得到递推公式(见下),同理可以求出最小的分数。

dp[i][j] = max(dp[i][k] + dp[k + 1][j]) + sum[j] - sum[i + 1]//后面的sum是前缀和

小结:

? 对于上面给出的dp的模式以及转移方程,发现确实符合区间型动态规划的特点,去头去尾 + 从短长度循环到长长度,只要有了以上几个共通点,代码就很容易得出了,这里就不给出了

能量项链


题面:


分析:

? 首先还是接环成串,发现还是合并的题目,我们仍然使用dp[i][j]表示第i颗珠子到第j颗珠子进行合并可以得到的最大值。

? 得到递推方程:

dp[i][j] = max(dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1])//左边珠子的值 + 右边珠子的值 + 两边珠子合并之后得到的值

小结:略


248 G


题面:


分析:

? 发现还是合并的问题,但是区间内的物体并不总是可以合并,为了方便表达我们使用dp[i][j]表达可以完全合并(最终变成一个)区间最终得到的值,最终只要取DP过程中得到的最大值即可

? 得到递推方程:

dp[i][j] = dp[i][k] + 1; 	if(dp[i][k] == dp[k + 1][j])

小结:略


涂色


题面:


分析:

? 直接设状态dp[i][j]为使区间内涂色与目标吻合的最少涂色次数,发现转移方程就很明显了

dp[i][j] = min(dp[i][k] + dp[k + 1][j]); //s[i] != s[j]
dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]); //s[i] == s[j]

注意初始条件,即区间长度为1的时候,此时满足dp[i][j] = 1;


小结:略