SSOJ2385合并石子
3273+
作者：crxis 发布：2017-10-23 分类：区间DP
题目大意：将n对石子合并成一堆，与合并果子不同的是，每次只能选相邻两堆进行合并，最小代价是多少？
题目描述
有一排石子，共n堆。现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分。
输入
第一行为一个正整数N（2<=N<=100);
以下N行，每行一个正整数，小于10000，分别表示第I堆石子的个数（1<=I<=N）。
输出
一个正整数，即最小得分。
样例输入
7
13
7
8
16
21
4
18
样例输出
239
解题思路
此题不能够用贪心，因为只能选相邻的两堆进行合并。如果看最终的结果，那么就是输出1到n这一段石子合并的总代价，最后一次合并的代价，是这n堆石子的重量之和，那么从哪里分开呢？可以在第2堆前面分开，也可以在第3、4、5、…、n堆前分开，不同的断点，前面的合并总代价可能不一样，选小的就像。我们发现，只要前面的长度短一点的石子合并代价算出来了，后面的就可以通过前面的推出来，因此我们可以从小到大枚举长度，一次把不同长度的石子合并的代价算出来。边界条件：1堆石子不需要合并，代价为0。
程序实现
f[i][j]表示长度为i，开头为j这一段石子合并的最小总代价。
f[i][j]表示i到j这一段石子合并的最小总代价。
记忆化搜索：
