记忆化搜索解决石子合并问题

#include<bits/stdc++.h>
using namespace std;
const int N = 305,inf = 0x3f3f3f3f;
typedef long long LL;
#define pb push_back
#define F(i,a,b) for(int i=a;i<=b;i++)
#define dF(i,b,a) for(int i = b;i>=a;i--)
// 状态 f[i][j]表示合并[i,j]区间的石子所需的最小代价
// 初始化 f[i][i] = 0
// 转移 f[i][j] = min(f[i][k]+f[k+1][j]+s[j]-s[i-1])
// 答案 ans = f[1][n]
int a[N],s[N],n,f[N][N];
int dfs(int l,int r)
{
    if(f[l][r] != inf) return f[l][r];
    for(int k = l;k<r;k++)
        f[l][r] = min(f[l][r],dfs(l,k)+dfs(k+1,r));
    f[l][r] += s[r]-s[l-1];
    return f[l][r];
}
int main()
{
    cin>>n;
    memset(f,0x3f,sizeof f);
    F(i,1,n)
    {
        f[i][i] = 0;
        cin>>a[i];
        s[i] = s[i-1]+a[i];
    }
    cout << dfs(1,n) << '\n';
    return 0;
}