区间dp及经典习题_区间dp经典题

前言

2024年的第一篇文章啊，也向大家送来一个迟来的新年祝福，接下来我将通过一些经典的习题来讲解一下区间dp

什么是区间dp（马嘉祺音）

区间dp就是以区间长度为阶段，由小的区间长度递推出大的区间长度的dp，口说无用，让我们见题说话吧

例题1：石子合并

这题他给出的条件是只能将相邻的两堆石子合并，所以跟合并果子有点差别，为什么不能再用贪心了？那我们就拿一组数据来证明一下

所以这题该怎么做呢，当然用我们这节课要学的知识点区间dp来做，我们设dp[i][j]为合并第i堆和第j堆的最小花费 所以状态转移方程为（以求最大值为例，最小值将max换为min即可）

dp[i][j] = max(dp[i][j] , dp[i][k] + dp[k+1][j] + sum[j] - sum[i - 1])(i <= k < j)

时间复杂度为O（n^3）能过普通版的石子合并

但怎么实现呢，这是就会有大可爱说先枚举起点，再枚举长度，再枚举断点，好！错了！比如说我们要推dp[1][4]需要dp[3][4]和dp[1][2],但我们根本就没求出来dp[3][4]，所以不对。在前面也说了，区间dp是以区间长度为阶段的dp，所以我们先枚举区间长度，在枚举起点，最后枚举断点k。

啊，对不起忘记了，当我们看到环的时候，我们应该先想到断环为链就是复制一份接到后面

AC代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n , a[N] , dpx[N][N] , dpn[N][N] , sum[N];
int main()
{
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d" , &a[i]);
		sum[i] = sum[i - 1] + a[i];//前缀和
		a[n + i] = a[i];//断环为链
	}
	for(int i = n + 1 ; i <= 2 * n ; i++)
	{
		sum[i] = sum[i - 1] + a[i];//继续做后面的前缀和
	}
	for(int k = 2 ; k <= n ; k++)//区间长度
	{
		for(int i = 1 ; i <= 2 * n - k; i++)//起点
		{
			int j = i + k - 1;//终点
			dpn[i][j] = 0x3f3f3f;
			dpx[i][j] = 0;
			for(int d = i ; d <= j - 1 ; d++)//断点
			{
				dpx[i][j] = max(dpx[i][j] , dpx[i][d] + dpx[d + 1][j] + sum[j] - sum[i - 1]);
				dpn[i][j] = min(dpn[i][j] , dpn[i][d] + dpn[d + 1][j] + sum[j] - sum[i - 1]);
			}
		}
	}
	int maxn = 0;
	int minn = 0x3f3f3f;
	for(int i = 1 ; i <= n ; i++)
	{
		maxn = max(maxn , dpx[i][i + n - 1]);
		minn = min(minn , dpn[i][i + n - 1]);
	}
	cout << minn << endl << maxn << endl;
	return 0;
}

例题2：加分二叉树

首先要说明一些性质，在一棵树的中序遍历中，根节点左面的都为他的左子树，右面的都为他的右子树 ，那么这题就似乎变得简单了，就是枚举根节点将树分成两块，在以此类推（反向石子合并）但是，这题的难点似乎不是第一问，而是第二问，我们怎么记录下那棵树呢？难道要把它建出来吗，当然不是啦，我们用root[i][j]记录在中序遍历第i个数到第j个数区间那一个是根，最后在二分跑一遍就行了（重点是问题二的实现方法想给大家看看）

AC代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
typedef long long ll;
ll n , a[N] , dp[N][N]  , root[N][N];
void print(ll l, ll r) 
{
	if (l > r) return;
	printf("%lld ", root[l][r]);
	if (l == r)return;
	print(l, root[l][r] - 1);
	print(root[l][r] + 1, r);
}
int main()
{
	scanf("%lld" , &n);
	for(int i = 1 ; i <= n ; i++) 
	{
		scanf("%lld" , &a[i]);
		root[i][i] = i;
		dp[i][i] = a[i];
		dp[i][i - 1] = 1;
	}
	for(int k = 1 ; k < n ; k++)
	{
		for(int i = 1 ; i <= n - k; i++)
		{
			int j = i + k;
			dp[i][j] = dp[i + 1][j] + dp[i][i];
			root[i][j] = i;
			for(int d = i + 1 ; d <= j - 1 ; d++)
			{
				if(dp[i][j] < dp[i][d - 1] * dp[d + 1][j] + dp[d][d])
				{
					dp[i][j] = dp[i][d - 1] * dp[d + 1][j] + dp[d][d];
					root[i][j] = d;
				}
			}
		}
	}
	cout << dp[1][n] << endl;
	print(1 , n);
	return 0;
}

思维拓展：矩阵取数游戏

思路简析：因为他每行之间没啥关系，所以分开处理，我们设dp[i][j]为每一行剩了第i到第j个数的最大值。所以状态转移方程为dp[i][j] = max(dp[i - 1][j] + d[i - 1] * 2^t ,  dp[i][j+1] + d[j+1] * 2^t)

具体的代码要自己实现哦毕竟是思维拓展

预告预告：接下来可能会讲树上dp，状态压缩dp，数学，树链剖分，插头dp等内容

好心人点点赞加加关注吧（初三生写文章不容易啊）