区间DP

引入

Problem Description

设有 N 堆石子摆成一条线，且每堆石子有一定的质量。现要将这 N 堆石子合并，并且规定每次只能合并相邻的两堆石子，合并的代价为两堆石子的重量，请输出合并所有石子为一堆的最小代价。

第一个想法:贪心

但就跟我们学习DP时遇到的情况一样，贪心算法的目光不够长远，所以接下来我们隆重介绍区间DP。

一. 定义

区间动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f(i,j)=(max){f(i,k)+f(k+1,j)+cost}, 其中cost 为将这两组元素合并起来的价值或代价。

二. 性质

区间 DP 有以下特点：

• 合并：即将两个或多个部分进行整合，当然也可以反过来；
• 特征：能将问题分解为能两两合并的形式；
• 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

三. 核心思路

就如同线性DP一般，要去找到一个大区间的最优解，我们就要先找到更小的区间的最优解以及边界，并且由题意找出状态转移方程，最终递推得到答案。

模板

for(int len = 2; len <= n; len++) # 设置区间长度
{
    
	for(int l = 1; l + len - 1 <= n; l++) # 设置左右端点
	{
    
		int r = l + len - 1;
		for(int k = l; k < r; k++) # 枚举分割点
		{
    
                    dp[l][r] = min(dp[l][r],dp[l][k] + dp[k+1][r] + cost)
		}
	}
}

例题

先来一道非常简单的区间DP，方便我们更加清晰的了解DP的特性

1.线性区间

Symmetric Mountains

Problem Description
Rebecca 有一张落基山脉的照片，上面排列着 N 座山，从左往右的高度是hi，Rebecca 截图保留照片的一个连续段，这张截图的不对称性定义为：处于截图上对称位置的山的高度差的绝对值之和（截图最左和最右的山的高度差，左数第二和右数第二的山的高度差，诸如此类的和）。
Rebecca 想要知道对于长度为 len (0 < len < N)的截图，拥有的最小不对称性。

第一种做法，直接模拟暴力

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e7+10;
const int INF = 0x3f3f3f3f;
int mout[N],dp[5005][5005];

void solve()
{
    
	int n;
	cin >> n;
	
	for(int i = 1;i <= n;i++) cin >> mout[i]; // 输入
	
	for(int len = 1;len <= n;len++) // 枚举长度
	{
    
		int ansmin = INF; // 初始化答案
		for(int l = 1; l + len - 1 <= n; l++)
		{
    
			int r = l + len - 1;
			
			int sum = 0;
			for(int i = l,j = l+len-1;i <= j;i++,j--) // 暴力！
				sum += abs(mout[i]-mout[j]);
			
			ansmin = min(ansmin,sum);
		}
		cout << ansmin << " "; // 输出答案
	}
}

int main()
{
    
	cin.tie(0) -> ios::sync_with_stdio(false);
	int t = 1;
	while(t--) solve();
	return 0;
}

然后喜提TLE

也许每次搜索并不需要如此费时？

参考答案
记录上一次更小的山脉的对称性再加上两端之差绝对值

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e7+10;
const int INF = 0x3f3f3f3f;
int mout[N],dp[5005][5005];

void solve()
{
    
	int n;
	cin >> n;
	
	for(int i = 1;i <= n;i++) cin >> mout[i]; // 输入
	
	for(int len = 1;len <= n;len++) // 枚举长度
	{
    
		int ansmin = INF; // 初始化答案
		for(int l = 1; l + len - 1 <= n; l++)
		{
    
			int r = l + len - 1;
			dp[l][r] = dp[l+1][r-1] + abs(mout[l]-mout[r]); // 状态转移方程
			ansmin = min(ansmin,dp[l][r]);
		}
		cout << ansmin << " "; // 输出答案
	}
}

int main()
{
    
	cin.tie(0) -> ios::sync_with_stdio(false);
	int t = 1;
	while(t--) solve();
	return 0;
}

回到我们引入的例题

石子合并 (弱化版)

Problem Description

设有 N 堆石子摆成一条线，且每堆石子有一定的质量。现要将这 N 堆石子合并，并且规定每次只能合并相邻的两堆石子，合并的代价为两堆石子的重量，请输出合并所有石子为一堆的最小代价。

参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int dp[305][305],Presum[N];

void solve()
{
    
	int n;
	cin >> n;
	
	memset(dp,0x3f,sizeof dp);  // 初始化为无穷大
	
	for(int i = 1;i <= n;i++)
	{
    
		int stone;
		cin >> stone;
		Presum[i] = Presum[i-1] + stone; // 前缀和优化
		dp[i][i] = 0; // 初始化为0
	}
	
	for(int len = 2;len <= n;len++) // 设置区间长度
	{
    
		for(int l = 1; l + len - 1 <= n; l++) // 设置左右端点
		{
    
			int r = l + len - 1;
			for(int k = l;k < r;k++)
			{
    
				// 状态转移方程
				dp[l][r] = min(dp[l][r],dp[l][k] + dp[k+1][r] + Presum[r] - Presum[l-1]);
			}
		}
	}
	
	cout << dp[1][n]; // 输出答案
	
}

int main()
{
    
	cin.tie(0) -> ios::sync_with_stdio(false);
	int t = 1;
	while(t--) solve();
	return 0;
}

存在的问题：
朴素的区间DP时间复杂度为O(n^3),在处理数据较大的题目时会超时

优化方案

四边形优化法

2.环形区间DP

石子合并

Problem description
设有 N 堆石子摆成一个圈，且每堆石子有一定的质量。现要将这 N 堆石子合并，并且规定每次只能合并相邻的两堆石子，合并的代价为两堆石子的重量，请输出合并所有石子为一堆的最小代价。

我们可以通过预处理将环形转换成线性

参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int dp[605][605],Presum[N],stone[N];

void solve()
{
    
	int n;
	cin >> n;
	
	memset(dp,0x3f,sizeof dp);  // 初始化为无穷大
	
	for(int i = 1;i <= n;i++)
	{
    
		cin >> stone[i];
		stone[i+n] = stone[i];
		dp[i][i] = dp[i+n][i+n] = 0; // 初始化为0
	}
	
	for(int i = 1; i <= 2*n; i++) Presum[i] = Presum[i-1] + stone[i]; // 前缀和优化
	
	for(int len = 2; len <= n; len++) // 区间长
	{
    
		for(int l = 1; l + len - 1 <= 2*n; l++) // 设置左右端点
		{
    
			int r = l + len - 1;
			for(int k = l;k < r;k++)
			{
    
				// 状态转移方程
				dp[l][r] = min(dp[l][r],dp[l][k] + dp[k+1][r] + Presum[r] - Presum[l-1]);
			}
		}
	}
	
	int ans = inf,ansmax = -inf;
	for(int i = 1; i <= n; i++)
	{
    
		ans = min(ans,dp[i][i+n-1]);
	}
	
	cout << ans << '\n'; // 输出答案
	
}

int main()
{
    
	cin.tie(0) -> ios::sync_with_stdio(false);
	int t = 1;
	while(t--) solve();
	return 0;
}

3.回文字符串

[IOI2000] 回文字串

Problem Description
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。
比如 Ab3bd 插入 2 个字符后可以变成回文词 dAb3bAd 或 Adb3bdA但是插入少于 2 个的字符无法变成回文词。

状态转移方程两种情况
1.首尾相同: 相当于可以直接删除头尾
2.首尾不相同: 找最小值

将非回文的字符个数从小区间扩展到大区间
参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3+10;
int dp[N][N];
char a[N];

void solve()
{
    
	string s;
	cin >> s;
	int n = s.size();
	for(int len = 2; len <= n; len++)
	{
    
		for(int l = 1; l + len - 1 <= n; l++)
		{
    
			int r = l + len - 1;
			if(s[l-1] == s[r-1])   // 字符串索引要-1,如果两端相同直接继承就好了
				dp[l][r] = dp[l+1][r-1]; 
				
			else
				dp[l][r] = min(dp[l+1][r],dp[l][r-1]) + 1;   //  两端不相同就找到更小的区间然后+1
		}
	}
	
	cout << dp[1][n];
}


signed main(){
    
	cin.tie(0)->ios::sync_with_stdio(false);
	int t = 1;
	while(t--) solve();
}

文章存在不足，欢迎各位dalao指出！

序号	题号	标题	题型	难度评级	题解
1	luogu P1775	石子合并（弱化版）	区间DP
2	luogu P1063	[NOIP2006 提高组] 能量项链	区间DP
3	luogu P1880	[NOI1995] 石子合并	区间DP
4	luogu P2858	[USACO06FEB] Treats for the Cows G/S	区间DP
5	luogu P9325	Symmetric Mountains	区间DP，模拟，枚举
6	luogu P1435	[IOI2000] 回文字串	区间DP，字符串
7	CodeForces 607B	Zuma	区间DP，字符串
8	luogu P4170	[CQOI2007] 涂色	区间DP
9	LightOj 1422	Halloween Costumes	区间DP
10	luogu P1140	相似基因	区间DP
11	HDU 4745	Two Rabbits	区间DP，回文串
12	luogu P3205	[HNOI2010] 合唱队	区间DP
13	HDU 2476	String painter	区间DP
14	luogu P1220	关路灯	区间DP

参考网站：

oiwiki

csdn

四边形不等式优化