区间dp-动态规划求解石子合并问题(c++实现)

#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int f[N][N];
int s[N];
int n;

int main(){
    scanf("%d",&n);
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        f[i][i]=0;
        s[i]+=s[i-1];
    }
    for(int len = 2;len <=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            for(int k=l;k<=r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    printf("%d",f[1][n]);
}