递推的本质是从小到大，所以区间dp是从小区间到大区间

题目描述
链接：https://ac.nowcoder.com/acm/problem/51170
来源：牛客网

解析和代码：
f[i][j] //子问题是i到j区间的最小的代价
#include<bits/stdc++.h>
using namespace std;
int n;
int a[305];
int f[305][305];
int main(){
cin >> n;
for(int i=1;i<=n;++i){
cin >> a[i];
a[i]+=a[i-1];
}
memset(f,0x3f,sizeof(f));
//f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
//动态规划意思是找到一个方程，然后可以从小一直推大，直到可知题目所求
//而究竟是什么状态从小到大，此题的状态如标题是区间，准确来说是这个区间合并的最小代价
//所以边界取决于从小到大的小
//以下两行：j表示区间右边界，i表示区间左边界，这样循环就能保证区间是从小区间到大区间的
for(int j=1;j<=n;++j){
for(int i=j;i>=1;--i){
if(i>=j) f[i][j]=0; //因为f数组初始化为了无穷大，所以边界要手动定义为0
for(int k=i;k<j;++k){
//以下注释是废话，不用看（打了那么多字舍不得删而已）
//k不能等于j,否则：会在转移方程转移时出现k比j大的情况,例如f[2][1]；并且会在区间长度为2时，进来2次，从而加了上一次的f[i][j],例如 i=1,j=2时，k会等于1(第一次进来) ，f[1][2]=f[1][1]+f[2][2]+... ,第二次进来k=2,f[1][2]=f[1,2]+f[2,2]+...。
//当然这是求最小值，所以等不等于没关系（其实求最大值也没关系），但还是规范一下自己的代码比较好
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
}
cout << f[1][n];
return 0;
}