区间Dp

状态的改变发生在一个区间里。
[eg.1] 石子合并：https://www.acwing.com/problem/content/284/

1.状态表示：f[i,j],表示从i到j，而不是两维。
(1)集合：所有将第i堆石子到第j堆石子的合并方式。
(2)属性：Min Loss 最小代价
2.状态计算：
以最后一次合并为基准，分为左右两堆，两堆的数目和为k(假设一共有k堆)
那么可以划分为：
1,k-1
2,k-2
……
k-1,1
于是可以得到最后一步状态计算的方程为：
f[i,j]=f[i,m]+f[m+1,j]+s[j]-s[i-1] (合并成最后一堆的代价是固定的所有石子的总重，利用前缀和来计算。)
时间复杂度：状态两维*枚举数n=O(n^3)

#include<iostream>
#include<algorithm>
using namespace std;

const int N=310,INF=1e9;

int f[N][N];
int n;
int s[N];

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

    for(int i=1;i<=n;i++) s[i]+=s[i-1];

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=INF;
            for(int k=l;k<r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n]<<endl; 
    return 0;
}