区间DP是线性DP的扩展，主要解决分阶段的划分问题

区间DP的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值

状态

属性

区间DP的状态属性一般为某种最值，追求价值最大或代价最小
集合

f[i][j]表示将下标位置i到j的所有元素合并能获得的价值的最大值

状态转移方程

f[i][j]=max{f[i][j],f[i][k]+f[k+1][j]+cost} （i<=k<j）

cost为将这两组元素合并起来得到的价值或需要付出的代价，通常结合前缀和处理

由于计算f[i][j]的值时需要知道所有f[i][k]和f[k+1][j]的值，而这两个中包含的元素的数量都小于f[i][j]，所以我们以len=j-i+1作为 DP 的阶段。首先从小到大枚举len，然后枚举i的值，根据len和i用公式计算出j的值，然后枚举k，时间复杂度为$O(n^3)$

处理环

将链延长一倍，变成len=2*n，其中第i堆和第n+i堆相同，求max{f(1,n),f(2,n+1)……f(i,n+i-1)}

核心代码

三步走：

枚举长度
枚举起点（起点结合长度，可得终点）
枚举分割点

for len in range(1,n+1):
    for i in range(1,n+2-len):
        l,r=i,i+len-1
        for k in range(l,r):
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+cost)

四边形不等式优化

区间DP的时间复杂度为$O(n^3)$，无法处理稍大数据量的题目

在查找最优分割点的时候，我们可以把最优分割点保存下来，在查找的时候利用保存的最优分割点来优化查找过程

核心：交叉小于包含

内容：对于a<b<=c<d，如果满足f[a][c]+f[b][d]<=f[a][d]+f[b][c]，则满足四边形不等式优化

结论（可以直接拿来用）：s[i][j-1]<=s[i][j]<=s[i+1][j]

参考内容:https://blog.csdn.net/noiau/article/details/72514812

282. 石子合并

设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 NN 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2，我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2，又合并 1，21，2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24；

如果第二步是先合并 2，32，3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式
第一行一个数 NN 表示石子的堆数 NN。

第二行 NN 个数，表示每堆石子的质量(均不超过 10001000)。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤N≤3001≤N≤300

输入样例：
1
2
>4
>1 3 5 2
输出样例：
1
>22

from itertools import accumulate

n=int(input())
nums=list(map(int,input().split()))
pre=[0,*accumulate(nums)]
dp=[[0 for _ in range(n+1)] for _ in range(n+1)]

for len in range(2,n+1):
    for i in range(1,n+2-len):
        l,r=i,i+len-1
        dp[l][r]=float('inf')
        for k in range(l,r):
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre[r]-pre[l-1])

print(dp[1][n])