区间dp

区间dp是动态规划的一个分支， 主要用于解决具有区间性质的问题，特别是涉及到区间的分割、合并或者区间间某种依赖关系的题目。

区间 DP 概念较好理解，实战的话主要是思考难度高一点点。思路可以总结为八个字：枚举断点，更新区间。

区间 DP 通常是由两个较小的区间合并答案转移成大区间的答案，因此转移方程通常为 $f_{i,j}=max(f_{i,j},f_{i,k}+f_{k+1,k})$

由于区间 DP 的转移通常为从两个较小的区间转移过来，因此我们需要先计算小空间的值，再计算较大空间的值。所以区间 DP 通常最外层循环就需要枚举区间长度。

石子合并

石子合并是一道区间dp的经典题目。这道题目和果子合并的最大区别就是需要合并相邻的石头。我们可以通过从小的区间的状态转移到大的区间。

对于一道区间dp题，我们第一维要枚举的是区间长度，因为需要从小的区间推算到大的区间，所以区间长度要从小的开始枚举。

第二维一般是起始位置，也就是你需要求的区间的起始位置，终止位置可以从起始位置+区间长度推出。

第三维是分割的位置，也就是当前求的区间要从哪两个区间推算而来。

我们假设，区间长度为len，起始位置为i，终止位置为j，枚举的分割点为k，$sum[i][j]$表示从i~j的石子个数和，则有以下的转移方程

$max(原来答案，左区间原来答案+右区间原来答案+合并消耗)$

//最大值
f[i,j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[i][j]);
//最小值
f[i,j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[i][j]);

通过这个转移方程，我们可以完成石子合并的核心代码

但是还有一点，石子是一个环，为了方便处理，我们采用把环变成两倍的长度来处理头尾衔接转移的问题（倍长思想）

for(int i=1;i<=n;i++){
   a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++){//预处理sum[i][j]
    for(int j=i;j<=n*2;j++){
        for(int k=i;k<=j;k++){
            sum[i][j]+=a[k];
        }
    }
}
int maxans=0,minans=1000000000;
for(int len=2;len<=n;len++){//枚举长度
    for(int i=1;i<=n*2-len+1;i++){//枚举起始点
        int j=i+len-1;//终止点通过起始点+长度来计算
        dp[i][j]=0;
        f[i][j]=1000000000;
        for(int k=i;k<j;k++){
            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[i][j]);
        }
    } 
}
for(int i=1;i<=n;i++){
    maxans=max(maxans,dp[i][i+n-1]);
    minans=min(minans,f[i][i+n-1]);
}