导读 ^ _ ^
区间DP是一种思考方式很不一样的DP问题。
结合合并石头进行问题思考，你就能学会区间DP啦！
何为区间DP
其DP推导是在一个区间内进行的，通常DP数组代表某个区间的某些属性。
当然，dp数组的推导非常麻烦。
需要依据某种特定的顺序，进行dp推导。
通常是 区间长度从小到大进行状态转移
合并石子
对于石头搬运的理解
最终的结果一定是两个合成一个，那么我们只要让合并的东西最小即可，如此递推下去。
推导状态转移
这里需要运用前缀和的思想，去舍掉无关石头的影响。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main( ) {
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&s[i]);
//前缀和处理
for(int i = 1; i <= n; i++) s[i] += s[i-1];
//从区间长度小的开始枚举,len初始为2
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] = 1e8;
for (int k = l; k < r; k++) //这里k<r
f[l][r] = min(f[l][k] + f[k+1][r] + s[r] - s[l-1],f[l][r]);
}
printf("%d",f[1][n]);
return 0;
}