动态规划(DP)——区间DP

设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22

package luogu.dp.区间DP;
import java.io.*;
public class 石子合并 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = in();//石子的堆数
        int[] s = new int[n+1];//石子的前缀和
        for( int i=1; i<=n; i++ ) {
            //计算石子的前缀和
            //后面合并两堆石子的消耗量等于两堆石头重量相加
            //前缀和可以直接计算
            s[i] = s[i-1]+in();
        }
        int[][] dp = new int[n+3][n+3];
        //合并n堆，先合并两堆，然后逐渐扩大
        //计算合并len堆石子的消耗，逐步扩大区间，len的取值 2-n
        //直至n
        for( int len=2; len<=n; len++ ){
            //区间开始的左下标
            //i+len-1 保证右下标不越界
            for( int i=1; i+len-1<=n; i++ ) {
                //遍历对区间的划分方式
                int l = i;//区间的左下标
                int r = i+len-1;//区间的右下标
                //先初始化为大数
                //以防默认值0影响后面，消耗肯定大于0
                dp[l][r] = 100000000;
                for( int k=l; k<r; k++ ) {
                    //对当前这个区间范围合并的最小值为
                    //前面的值   与   当前划分方法 合并两个区间的消耗加上两个区间之前各自合并的消耗
                    //取最小值
                    //dp[l][r] 前面划分方式的最小值
                    // dp[l][k] 合并成左区间的最小消耗 + 
                    // dp[k+1][r] 合并成右区间的最小消耗 +
                    // s[r]-s[l-1] 左右这两个区间合并的消耗
                    dp[l][r] = Math.min( dp[l][r], dp[l][k]+dp[k+1][r]+s[r]-s[l-1] );
                }
            }
        }
        out.println(dp[1][n]);
        out.flush();
    }
    public static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}