掰开！！！--洞洞拐

（宇宙免责声明：因为本人在$luogu$网校之前并未跟随老师系统的学过$DP$(zy背锅)，又加之上课时肚子疼没怎么听，导致这篇文章完全是我刚刚(2025·8·9 16:30~16:55)拉💩时自己思考对区间$DP$的理解，若有错误，欢迎指正）

区间$DP$是基于分治思想(应该是吧)求解问题的一种动态规划模型，它的做法十分通俗易懂，即用小区间合并成大区间最后得到整个区间的最优解

区间$DP$一般有很明显的标志->相邻两数合并，这也是区间$DP$的核心操作，通过求解每个子段的最优解并拼接得到新的最优解

---

我在这说也没用，上例题：石子合并，看下代码

//f[i][j]代表把i->j合并所用的最小花费
for( int i=1;i<=n;i++ ) f[i][i]=0;//初始化：将i->i合并不用花费
for( int len=2;len<=n;len++ )//枚举区间长度
    for( int l=1, r=l+len-1;r<=n;l++, r++ )//枚举区间
        for( int k=l;k<r;k++ )//枚举中间的断点->合并时左区间的右端点
            f[l][r]=min( f[l][r],f[l][k]+f[k+1][r]+pre_sum[r]-pre_sum[l-1] );//转移

看了代码是不是豁然开朗？区间$DP$的式子基本如此：$枚举左端点->枚举右端点->转移$

写成代数式为$f[i][j]=\{max,min\}_{k=i}^{j-1}(f[i][k]+f[k+1][j]+value),i \in [1,n-1],j \in [i+1,n]$(value代表合并的花费)，大多区间$DP$的转移方程都与它相似甚至相同

---

但在部分情况，我们需要对数组进行一些修改后再进行$DP$，例如能量项链

这时候，我们要进行$DP$的部分是一个环，不好直接在原数组上进行$DP$，所以我们要断环成链，将原数组复制一份放在后面

这样处理后，数组中任一长度为$n$的子段都是原环的一种可能，代码如下

for( int i=1;i<=n;i++ ) cin>>power[i], power[i+n]=power[i];//断环成链
for( int len=2;len<=n;len++ )
    for( int l=1, r=l+len-1;r<=2*n;l++, r++ )
        for( int k=l;k<r;k++ )
            f[l][r]=max( f[l][r],f[l][k]+f[k+1][r]+power[l]*power[k+1]*power[r+1] );
int ans=0;
for( int i=1;i<=n;i++ ) ans=max( ans,f[i][i+n-1] );//答案是n个断出的长度为n的子段中的最大值

断环成链是区间$DP$中一个十分重要的技巧，它可以将不好处理的环上问题转化为线性的问题，是处理区间$DP$问题中经常需要考虑的点(出题人也喜欢考)