浅谈区间DP

· · 个人记录

本人最近学习DP，尤其研究区间DP，所以水了这篇博文，来记录自己的颓废学习过程

区间DP，顾名思义，就是在区间上进行动态规划，求解一段区间上的最优解。通过合并小区间得出整个区间的最优解的一种DP。

区间DP的用法较为固定，形式应该也较为容易看出

区间DP通常思路（模板

首先根据数据得出解答数组的维度，之后根据维度进行长度的枚举，在此之后枚举起点，得出终点（高维数组也可以此类推，枚举出区间，在区间所给定范围内枚举合并点（分割点），通过状态转移公式得出该区间内的最优解存入数组中，得出答案（以上操作可以称为DP操作）

关于DP初始化

好像没什么好说的，就是要求什么就将什么初始化就是了

关于DP顺序

DP的顺序一般都是要经过耐心揣摩的，通常遵循不重不漏的原则，也就是说，我们当前的求解的集合中所包含的情况，必须是先前所计算出来的，否则，这个DP很有可能就是有问题的DP操作，（玄学除外hh） 因为它所求的解答的集合中，有些集合是空的，也就是没有按照DP的基本思路和要求进行求解（建议可以看一下yxc的闫氏DP分析法，B站或者AcWing应该都能找到？） 所以DP的顺序是要通过仔细考量得出的，否则辛辛苦苦推出一个方程结果因为这些问题爆了岂不是很可惜？不过还要注意一下循环的起点和终点，这些细节也值得去揣摩，不过本人觉得特殊值思考更容易想通。

关于DP方程

区间DP方程基本是固定的，题目做多了就会发现一些固定规律

关于DP答案求解

主要视题目内容而定，一般就是f[1][n]这种应该，不过可以注意一下破环成链的时候是要一个1-n的循环枚举找的，参见P1880 [NOI1995] 石子合并

例题

P1040 [NOIP2003 提高组] 加分二叉树

题目求解

一道基础的区间DP问题，我们考虑DP中的几个要素：

状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。

状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树集合按根节点分类，则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k + 1][j] + w[k]，则f[i][j]即为遍历k所取到的最大值。

然后记录下每个节点的最大值及编号就行了。

状态总数是 O(n^2)，计算每个状态需要 O(n) 的计算量，因此总时间复杂度是 O(n^3)。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[50],f[50][50],g[50][50];
void out(int l,int r) {
    if(l>r)
        return ;
    cout<<g[l][r]<<' ';
    out(l,g[l][r]-1);
    out(g[l][r]+1,r);
}
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];

    for(int len=1; len<=n; len++)
        for(int l=1; l+len-1<=n; l++) {
            int r=l+len-1;
            if(len==1) f[l][r]=a[l],g[l][r]=l;
            else
                for(int k=l; k<=r; k++) {
                    int left1,right1,fen;

                    if(k==l)
                        left1=1;
                    else
                        left1=f[l][k-1];

                    if(r==k)
                        right1=1;
                    else
                        right1=f[k+1][r];

                    fen=left1*right1+a[k];

                    if(f[l][r]<fen) f[l][r]=fen,g[l][r]=k;
                }
        }

    cout<<f[1][n]<<endl;
    out(1,n);
}

例题二

P1063 [NOIP2006 提高组] 能量项链

题目求解

和石子合并类似，只不过感觉相对石子合并来说题目描述更加晦涩（至少我读小学时是这么认为的），我们将能量珠的头标记记为a[i]，我们首先可以知道相邻两个能量珠合并时放出的能量值有且只有一个值，就是a[i]*a[i]*a[i+1]这就是我们初始化的一部分（不过也可以忽略这一步，之后的循环多加一层就是），还有数组归零，这就是我们所做的初始化

DP操作，首先枚举区间长度len，从3到n枚举，记f[i][j] 为将i-j个珠子合并为一个珠子所得的最大能量值 ，易得DP方程

f[i][j]=max(f[i][j],f[i][k]+f[k+a[j]+a[i]*a[k+1]*a[j+1]);

之后一个破环成链的技巧，将环形问题解决。

本人丑陋代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int ans,a[maxn],n,f[maxn][maxn];
int main() {

    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>a[i];
        a[i+n]=a[i];
    }

    for (int i=1; i<2*n; i++)
        f[i][i+1]=a[i]*a[i+1]*a[i+2];

    for (int len=3; len<=n; len++) {
        for (int i=1; i+len-1<=n*2; i++) {
            int j=i+len-1;
            for (int k=i; k<j; k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
        }
    }

    for (int i=1; i<=n; i++)
        ans=max(ans,f[i][i+n-1]);
    cout<<ans<<endl;
}

例题三

P6879 [JOI 2020 Final] スタンプラリー 3 逆时针和顺时针取的黑白熊雕像是两种不同的状态，所以需要两个维度确定，还有时间和方向的左边或者右边，确定了状态 f[l][r][k][0/1]f[l][r][k][0/1]为左边取到ll个和右边rr个，最终取到kk个不炸的雕像，且在左边/右边的时间

之后分类讨论，确定当在左边时向左/右取雕塑的情况和在右边的情况，4种情况4个方程，得出答案

代码：

#include <bits/stdc++.h>
#define maxn 255
#define int long long
using namespace std;
int f[maxn][maxn][maxn][2],n,ll,ans,a[maxn],t[maxn];
signed main() {
    cin>>n>>ll;
    for (int i=1; i<=n; i++) cin>>a[i];
    a[n+1]=ll;
    for (int i=1; i<=n; i++) cin>>t[i];
    memset(f,0x3f,sizeof f);
    f[0][0][0][0]=f[0][0][0][1]=0;
    for(int l=0; l<=n; l++)
        for(int r=0; r<=n; r++) {
            if(l+r>=n)break;
            for(int k=0; k<=n; k++) {
                int tmp=f[l][r][k][0];
                if(tmp<=1e13) {
#define f1 f[l+1][r][k+(tmp+a[n-l+1]-a[n-l]<=t[n-l])][0]
                    f1=min(f1,tmp+a[n-l+1]-a[n-l]);
#define f2 f[l][r+1][k+(tmp+ll-a[n-l+1]+a[r+1]<=t[r+1])][1]
                    f2=min(f2,tmp+ll-a[n-l+1]+a[r+1]);
                }
                tmp=f[l][r][k][1];
                if(tmp<=1e13) {
#define f3 f[l+1][r][k+(tmp+ll-a[n-l]+a[r]<=t[n-l])][0]
                    f3=min(f3,tmp+ll-a[n-l]+a[r]);
#define f4 f[l][r+1][k+(tmp+a[r+1]-a[r]<=t[r+1])][1]
                    f4=min(f4,tmp+a[r+1]-a[r]);
                }
            }
        }
    for (int i=0; i<=n; i++)
        for (int j=0; j<=n; j++)
            for (int k=0; k<=n; k++)
                if(min(f[i][j][k][0],f[i][j][k][1])<1e15)ans=max(ans,k);
    cout<<ans<<endl;
    return 0;
}

尾声

总的来说，区间DP的题目，套路基本固定，可是需要一些细节处理，总的来说还是有思维难度的，本博文后期还会更新