分治

如图，该题是美团2021春招笔试题。当时做卷子想复杂了，觉着一个中序序列构建的树有多种可能，每种可能都得计算出开销，同时记录下最小开销。直接爆炸。后来看题解才觉悟是一个经典的分治问题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 310;
const int inf = 1<<30;

vector<int>v(maxn,0);
//备忘录
int vis[maxn][maxn][maxn];
//以father为根节点能够得到的最优树
int dp(int l,int r, int father){
    if(l>r) return 0;
    if(vis[l][r][father]!=-1) return vis[l][r][father];
    int ret = inf;
    // 这些节点中每个均可能做根 需要遍历一下
    for(int i=l;i<=r;++i){
        //递归计算左右子树的最小代价
        int left = dp(l,i-1,i);
        int right = dp(i+1,r,i);
        // 总最小=min(左子树+右子树+选出的根节点值*father节点值)
        ret = min(ret,left+right+v[i]*v[father]);
    }
    //备忘录记下已经取得的值
    return vis[l][r][father]=ret;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>v[i];
    memset(vis,-1,sizeof(vis));
    int ans = dp(1,n,0);
    printf("%d\n",ans);
    return 0;
}