本人最近学习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] 石子合并
例题
题目描述
设一个 $n$ 个节点的二叉树 $tree$ 的中序遍历为$(1,2,3…n)$，其中数字$1,2,3…n$为节点编号。每个节点都有一个分数（均为正整数），记第$i$个节点的分数为 $d_i$，$tree$及它的每个子树都有一个加分，任一棵子树$subtree$（也包含$tree$本身）的加分计算方法如下：
$$subtree的左子树的加分×subtree 的右子树的加分+subtree 的根的分数$$
若某个子树为空，规定其加分为 $1$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为 $(1,2,3,…,n)$ 且加分最高的二叉树 $tree$。要求输出
$1.$ $tree$ 的最高加分。
$2.$ $tree$ 的前序遍历。
输入格式
第 $1$行 $1$ 个整数 $n$，为节点个数。
第 $2$ 行 $n$ 个用空格隔开的整数，为每个节点的分数
输出格式
第 $1$ 行 $1$ 个整数，为最高加分 $（Ans≤4,000,000,000）$。
第 $2$ 行 $n$ 个用空格隔开的整数，为该树的前序遍历。
输入输出样例
输入#1:
5
5 7 1 2 10
输出#1:
145
3 1 2 4 5
说明/提示
数据规模与约定
对于全部的测试点，保证$1≤n<30$,节点的分数是小于$100$的正整数，答案不超过$4×10^9$
题目求解
一道基础的区间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);
}
例题二
题目描述
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\oplus$ 表示两颗珠子的聚合操作，$(j \oplus k)$ 表示第 $j,k$ 两颗珠子聚合后所释放的能量。则第 $4$ 、 $1$ 两颗珠子聚合后释放的能量为：
$(4 \oplus 1)=10 \times 2 \times 3=60$。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：
$((4 \oplus 1) \oplus 2) \oplus 3)=10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710$。
输入格式
第一行是一个正整数 $N$（$4 \le N \le 100$），表示项链上珠子的个数。第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$。第 $i$ 个数为第 $i$ 颗珠子的头标记（$1 \le i \le N$），当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记。第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出格式
一个正整数 $E$（$E\le 2.1 \times 10^9$），为一个最优聚合顺序所释放的总能量。
输入样例 #1
4
2 3 5 10
输出样例 #1
710
说明
NOIP_2006_提高组_第一题
题目求解
和石子合并类似，只不过感觉相对石子合并来说题目描述更加晦涩（至少我读小学时是这么认为的），我们将能量珠的头标记记为$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
题目描述
给定一个周长为 $L$ 的圆，从一个点出发，有 $N$ 个黑白熊雕像，编号为 $1$ 到 $N$，第 $i$ 个雕像在顺时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。
现在 JOI 君在这个点，他每一秒可以移动一米，并且他可以顺时针或者逆时针的移动。
JOI 君想问，他最多能收集到多少个黑白熊雕像？
输入格式：
第一行两个整数 $N,L$ 代表雕像数和圆的周长。
第二行 $N$ 个整数 $X_i$ 代表每个雕像在顺时针多少米处。
第三行 $N$ 个整数 $T_i$ 代表每个雕像需要在多少秒内拿到。
输出格式：
一行一个整数代表答案。
输入样例#1：
6 25
3 4 7 17 21 23
11 7 17 10 8 10
输出样例#1：
4
输入样例#2：
5 20
4 5 8 13 17
18 23 15 7 10
输出样例#2：
5
输入样例#3：
4 19
3 7 12 14
2 0 5 4
输出样例#3：
0
输入样例#4：
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
输出样例#4：
5
说明
样例 1 解释
JOI 君可以按照如下策略拿到 $4$ 个黑白熊雕像：
| 方向 | 路程 | 总时间 | 第几个雕像 | 能否拿到 |
|---|---|---|---|---|
| 逆时针 | $2$ 米 | $2$ 秒 | $6$ | $可以$ |
| 逆时针 | $2$ 米 | $4$ 秒 | $5$ | $可以$ |
| 顺时针 | $7$ 米 | $11$ 秒 | $1$ | $可以$ |
| 顺时针 | $1$ 米 | $12$ 秒 | $2$ | $不可以$ |
| 顺时针 | $3$ 米 | $15$ 秒 | $3$ | $可以$ |
样例 2 解释
JOI 君可以直接一直逆时针走。
样例 3 解释
JOI 君无法得到任何一个雕像。
数据规模与约定
本题采用捆绑测试。
- Subtask 1（5 pts）：$N \le 12$，$L \le 200$，$X_i \le 200$。
- Subtask 2（10 pts）：$N \le 15$。
- Subtask 3（10 pts）：$L \le 200$，$T_i \le 200$。
- Subtaks 4（75 pts）：无特殊限制。
对于 $100\%$ 的数据：
- $1 \le N \le 200$。
- $2 \le L \le 10^9$。
- $1 \le X_i<L$。
- $X_i < X_{i+1}$。
- $0 \le T_i \le 10^9$。
逆时针和顺时针取的黑白熊雕像是两种不同的状态，所以需要两个维度确定，还有时间和方向的左边或者右边，确定了状态
$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的题目，套路基本固定，可是需要一些细节处理，总的来说还是有思维难度的，本博文后期估计还会更新
