区间DP问题常常涉及到区间的合并与分裂,下面记录几个比较经典的区间DP例题。
解决问题的关键就是在进行递推时由小区间去推大区间的值,在最外层枚举区间长度。
石子合并与环形石子合并
f[i][j]
表示将第i个区间到第j个区间合并的最大/最小价值
for(int len = 2; len <= n; ++len){ // 先枚举区间长度
for(int l = 1; l + len - 1<= n; ++l){ // 再枚举区间左端点
int r = l + len - 1; // 直接计算出区间右端点
// 如果求最小价值需要初始化成正无穷 f[l][r] = INF;
for(int k = l; k < r; ++k){ // 枚举区间分裂点,将大区间分裂成小区间
f[l][r] = max(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k + 1 - 1]) + (s[k] - s[l - 1]));
// 这里s数组维护的是区间前缀和
}
}
}
首先我们考虑如何将环形石子联系到石子合并。
对于一个环,我们只要找一点进行切割就可以使它变成链,再去对链使用石子合并。
但是在这种情况下,除非链头和链尾是最后合并的两堆石子,否则一定会丢失一些决策情况。
我们只需要枚举不同切割点再取最值就可以了,虽然会重复,但是不会遗漏,不影响最大/最小值的正确性。
为了优化时间复杂度,环形石子合并类题目我们会用到一种的将环转化成链的方法:复制数组。
即在读入数据时进行以下操作:
for(int i = 1; i <= n ; ++i){
scanf("%d",&q[i]);
q[i + n] = q[i];
}
然后我们从头开始取长度为n的区间进行合并,就可以不遗漏地枚举所有将环切割成链的情况。
for(int len = 2; len <= n; ++len){
for(int i = 1; i + len - 1 < 2*n; ++i){ // 这里区间的尾部最大可以到2n,下面的做法和石子合并完全相同
int j = i + len - 1;
f[i][j] = -INT_MAX;
g[i][j] = INT_MAX;
for(int k = i; k < j; ++k){
g[i][j] = min(g[i][j],g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
最后求答案时还需要再枚举一下所有可能的切割方案。
int res1 = -INT_MAX,res2 = INT_MAX;
for(int l = 1; l <= n - 1; ++l){
int r = l + n - 1;
res1 = max(res1,f[l][r]);
res2 = min(res2,g[l][r]);
}
环形石子合并与最优矩阵链乘
这里涉及到环形的问题因此也需要用到我们前面将环转化成链的方式:复制数组再进行n长度的枚举
在最优矩阵链乘类型的题目中我们的状态变量可以采用前矩阵或后矩阵的一维,具体实现方式如下:
f[i][j]
表示将i点到j点合并的最大值,这里的点就是能量珠的一端。
状态转移方程为:f[i][j] = max(f[i][j],f[i][k] + f[k][j] + q[i]*q[k]*q[j]);
C++ Code:
#include <iostream>
using namespace std;
const int N = 210;
int n,q[N],f[N][N];
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n ; ++i){
scanf("%d",&q[i]);
q[i + n] = q[i];
}
for(int len = 2; len <= n + 1; ++len){
for(int i = 1; i + len - 1 <= 2*n; ++i){
int j = i + len - 1;
for(int k = i + 1; k < j ; ++k){
f[i][j] = max(f[i][j],f[i][k] + f[k][j] + q[i]*q[k]*q[j]);
}
//printf("f[%d][%d] = %d\n",i,j,f[i][j]);
}
//puts("");
}
int res = 0;
for(int i = 1; i <= n; ++i){
int j = i + n;
res = max(res,f[i][j]);
}
printf("%d\n",res);
return 0;
}
与树相关的区间DP
与树相关的区间DP问题和树形DP的最大区别是,树形DP节点和边的关系都是基本确定的,而前者一般会给出某种顺序的遍历结果的列表,树中节点和边的关系没有确定,求解的是一个最优的树形结构。
以中序遍历为例,我们还是从小区间递推大区间这个方向入手。
f[l][r]
表示以l~r为中序遍历的子树的最大价值。
先枚举区间长度,再枚举区间左端点,然后我们枚举根节点的位置。
剩下的具体细节根据题目要求完成。
如果这里还需要进行方案记录和打印,我的处理方式是开一个root[l][r]
数组,在计算最优价值时记录最优的根节点,通过递归打印树的其他遍历形式。
前序遍历
void printTree(int l,int r){
int root = Root[l][r];
printf("%d ",root);
if(root - 1 >= l)printTree(l,root - 1);
if(root + 1 <= r)printTree(root + 1,r);
}
后序遍历
void printTree(int l,int r){
int root = Root[l][r];
if(root - 1 >= l)printTree(l,root - 1);
if(root + 1 <= r)printTree(root + 1,r);
printf("%d ",root);
}