石子合并
设有 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≤300
输入样例：
4
1 3 5 2
输出样例：
22
经典区间dp问题：
状态表示：采用二维数组，f[i] [j] 表示的是合并了从i到j的石子之后，所得到的最小代价.最后答案的表示即为f[1] [n] .
状态属性： min
base case:
状态转移：因为我们选定的状态其实是一段区间的最小状态，所以我们先要选取区间用len来表示，然后对于每一个区间内部来说.
我们考虑到每一个区间所谓的最小代价，最后必将是左边一个连续的集合与右边一个连续的集合进行相加，这两个集合同时也是可以用我们的f数组来表示，这也就是我们这一题可以用dp来做的原因。我们采用设置一个k，来作为起点和终点的一个中断点，通过对k在i到j(即每个区间)的放置位置，来选择局部最优的方式。最终，不断迭代，即可得到最终的答案。
不说了，上代码：
#include
using namespace std ;
const int N = 310 ;
int f[N][N] ;
int w[N] ;
int main()
{
int n ;
cin >> n ;
for(int i = 1 ; i <= n ;++i)
{
cin >> w[i] ;
w[i] += w[i-1] ;
}
for(int len = 2 ; len <= n ; ++len)
{
for(int i = 1 ; i <= n + 1 -len; i ++)
{
int j = len + i - 1 ;
f[i][j] = 1e9 ;
for(int k = i ; k < j ;++k)
{
f[i][j] = min(f[i][j] , f[i][k]+f[k+1][j]+ w[j] -w[i-1]) ;
}
}
}
cout << f[1][n] << endl ;
return 0 ;
}
