一、基本概念

1、链式区间dp
for(int len = 2; len <= n; len++){ //枚举区间长度
		for(int i = 1; i + len - 1 <= n; i++){//枚举左边界
			int j = i + len - 1; //有边界
			for(int k = i; k < j; k ++){ // 中间变量位置
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost[i][j]);
			}
		}
	}
2、环形区间dp:把范围扩大一倍,从f[1][n],f[2][n + 1]中寻找最优解

image

3、关于区间dp的更新状况

每次对固定区间长度进行更新,更新顺序遵循由小区间到大区间。

二、区间dp适用情况

image

三、相关题目

1、Zuma
#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int dp[N][N], a[N], n;
//dp[i][j]表示合并区间[i][j]所需要的最少步数

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	memset(dp, 0x3f, sizeof dp);
	for(int i = 1; i <= n; i++){
		dp[i][i] = 1;
		if(a[i] == a[i + 1]) dp[i][i + 1] = 1;
		else dp[i][i + 1] = 2;
	}
	for(int len = 2; len <= n; len++){
		for(int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			//必须要有j - i > 1,因为j - i == 1这种情况在初始化已经被更新了,且是最优值
			//为什么当相等的时候,直接由dp[i+1][j-1]转移过来呢?
			//因为区间[i+1,j-1]合并到最后会剩下一个回文串,回文串两端加上相同的字母还是回文串,合并次数不变 
			if(a[i] == a[j] && j - i > 1) {
				dp[i][j] = dp[i + 1][j - 1];
			}
			for(int k = i; k < j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}
2、Minimum Triangulation

简单区间dp

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 510;
int dp[N][N], a[N], n;

signed main(){
	cin >> n;
	memset(dp, 0x3f, sizeof dp);
	for(int i = 1; i <= n; i++){//区间内只有一个数或者区间内只有两个数,不能组成三角形
		dp[i][i] = 0;
		dp[i][i + 1] = 0;
	}
	for(int len = 2; len <= n; len++){
		for(int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			for(int k = i; k < j; k++){//其他题目区间是不包含关系,所以是k+1
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + i * k * j);
			}
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}
3、Array Shrinking

思路非常棒的一道题,代码量比较小,不好想

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 510;
int dp[N][N], a[N], n;//dp表示区间长度(即区间内所剩余的数的个数)
int v[N][N];//记录区间[i][j]合并后所剩的一个数的值(如果可以)

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		v[i][i] = a[i];//注意这个敌方的初始化
	}
	memset(dp, 0x3f, sizeof dp);
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			dp[i][j] = j - i + 1;//求区间长度
		}
	}
	for(int len = 2; len <= n; len++){
		for(int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			for(int k = i; k < j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
				if(dp[i][k] == 1 && dp[k + 1][j] == 1 && v[i][k] == v[k + 1][j]){//合并条件还是蛮好理解的
					dp[i][j] = 1;
					v[i][j] = v[i][k] + 1;
				}
			}
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}
4、Clear the String

这个状态转移方程写的太妙了!爱了爱了。
image

5、矩阵取数游戏

image

参考博客:

1、https://www.cnblogs.com/ljy-endl/p/11610549.html
2、https://blog.csdn.net/Gonhz/article/details/105361300
3、https://www.luogu.com.cn/problem/solution/CF1132F
4、https://blog.csdn.net/m0_57344422/article/details/118085490

原文地址:http://www.cnblogs.com/N-lim/p/16905349.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性