1. 树形DP。
  2. 备忘录减少算法复杂度（-1）说明没有访问过。里面保存的就是最小，所以直接用就行
  3. father这个假节点很重要。 
#include<bits/stdc++.h>
using namespace std;
const int maxN = 301;
vector<int> nodes;
int ans[maxN][maxN][maxN];//动态转移方程

int dp(int l ,int r, int father){
    //base case
    if(l>r) return 0;//这个树的根目前在最左边，没有左子树
    //备忘录剪枝(如果以及有了结果，啧直接返回这个结果)
    if(ans[l][r][father]!=-1) return ans[l][r][father];


    int res = INT_MAX;
    // 这些节点中每个均可能做根 需要遍历一下
    for(int i = l;i<=r;i++){

        //分别作为father，左子树遍历的结果，以及对应右子树遍历的结果
        int left = dp(l,i-1,i);
        int right = dp(i+1,r,i);
        // 总最小=min(左子树+右子树+选出的根节点值*father节点值)
        res= min(res,left+right+ nodes[i]*nodes[father]);

    }


    //备忘录记下已经取得的值
    return ans[l][r][father] = res;



}

int main(){
    int N,x;

    while(cin>>N){
        nodes.clear();
        nodes.push_back(0);//放入假根
        for(int i =0; i<N;i++){
            cin>>x;
            nodes.push_back(x);
        }

        memset(ans,-1,sizeof(ans));//默认都为-1
        int res = dp(1,N,0);//编号从1，n结点中 轮流取根节点划分左右树，且这个根和0节点链接的最小权重

        cout<<res<<endl;
    }


    return 0;
}