一、基本概念
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]中寻找最优解
3、关于区间dp的更新状况
每次对固定区间长度进行更新,更新顺序遵循由小区间到大区间。
二、区间dp适用情况
三、相关题目
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
这个状态转移方程写的太妙了!爱了爱了。
5、矩阵取数游戏
参考博客:
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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性