区间dp

例题:https://www.acwing.com/problem/content/284/
简易描述：有N堆石子，将N堆石子合并成一堆，只能合并相邻两堆石子，选择的总代价为两堆石子总和。

#include<bits/stdc++.h>
using namespace std;
const int N =305;
int pre[N];
int dp[N][N];//合并区间i,j的最小值。
int n;
const int inf =INT_MAX/2;
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pre[i], pre[i] +=pre[i-1];
    //枚举区间最小值
    for(int len=2;len<=n;len++)
    {
        //枚举左区间
        for(int i=1;i+len-1<=n;i++)
        {
            int j =i+len-1;//右端点。
            dp[i][j] = inf;//初始化成最大值
            for(int k=i;k<=j;k++)//枚举中间的分界点
            {
                //状态转移计算最小值
                dp[i][j] =min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
}