石子合并(简单版)

先看题目：https://ac.nowcoder.com/acm/problem/51170
题目描述：
N堆石子排成一排，每次可以合并相邻的两堆，每次合并得分为合并的两堆石子之和，问把所有石子合成一堆的最小得分是多少？
解题思路：
区间dp入门题，dp[i][j]表示从i到j合并的最小得分，则可写出状态转移方程：

dp[i][j] = min( dp[i][j], dp[i][k]+dp[k+1][j]+sum(i,j) )

注：
1.由于要求最小得分，dp初始化为inf，
2.由转移方程可以看出，要求(i,j)这个区间需要比它区间长度小的那些区间的状态。故for循环第一层枚举长度，第二层枚举区间起点，则区间终点可知，然后枚举区间的间隔点k。
3.sum(i,j)可以使用前缀和来实现。

代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[500];
int sum[500];
int dp[500][500];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp, inf, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        sum[i] = sum[i-1]+a[i];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    for(int l = 2; l <= n; l++) {   //区间长度
        for(int i = 1; i <= n; i++) {   //枚举起点
            int j = i+l-1;  //区间终点
            if(j > n) break; //越界结束
            for(int k = i ; k < j; k++) {   //枚举分割点，构造状态转移方程
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    printf("%d\n",dp[1][n]);
}