题目描述

石子合并

j-i的阶乘个方案

利用了dp左右分段（变化的和不变的）、前缀和思想

区间问题（循环）
(1)枚举区间长度
(2)枚举左端点
(3)枚举右端点

C++ 代码

#include<iostream>

using namespace std;

const int N=310;
int n;
int f[N][N];  //状态数
int s[N];   //前缀和   为了方便我们求某一段的和
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];   //读入数字并计算总代价

    for(int len=2;len<=n;len++)   //枚举区间长度
    {
        for(int i=1;i+len-1<=n;i++)   //枚举区间左端点
        {
            int j=i+len-1;   //右端点
            f[i][j]=1e8;
            for(int k=i;k<j;k++)   //右边一堆  [i,j)

            //左右两堆分别加起来，最后再加上总和
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);//计算给定区间[i,j]的前缀和
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}