1

树的问题 要么就是递归 要么就是左右子树分治
最优问题 想到最优子结构 动态规划
如何使用动态规划做出这道题
首先找最优子结构
只有数值小于等于两个节点时 不用考虑 直接为a*b
考虑简单的情况 1,2,3
可能有三种情况 要依次遍历
1为根 1*2 + 1*3
2为根 1*2 + 2*3
3为根 1*3 + 3*2
选择根节点，分别计算出每个根节点的最优值 然后选出最优的

所以对于有很多值的
把每个点都作为根节点 然后左右子树分治 分别求出最优解

定义 转移状态
首先 有一个范围 l,r
然后dp[l,r]表示 遍历i属于[l,r] 以i为根节点的所代表的最小值
min(dp(l,i-1) + im + in + dp(i+1,r))
m 代表dp(l,i-1) 最优选出的 根节点
n 代表 dp(i+1,r)最优选出的 根节点
所以根节点应该把两个值中较小的值放到根节点

package test;

import java.util.Scanner;
import java.util.*;
import java.io.*;


public class Main{


    private static int[] seq;

    public static void main(String[] args) {

        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt();

        seq = new int[n+1];

        for(int i=0;i<n;i++){
            seq[i] = sc.nextInt();
        }
        seq[n] = Integer.MAX_VALUE;
        int res =  dp(0,n-1)[0];
        System.out.println(res);


    }

    public static int[] dp(int l, int r){
        //res[0] 该序列最小值 res[1] 最小值对应的根节点
        if(l == r) return new int[]{0,l};
        if(l+1 == r){
            return new int[]{seq[l]*seq[r],l};
        }


        int res_0 = Integer.MAX_VALUE;
        int res_1 = seq.length-1;

        for(int i=l; i<=r ;i++){
            if(i==l){
                int[] VandN = dp(i+1,r);
                int temp = VandN[0] + seq[i]*seq[VandN[1]];
                if(temp <= res_0) {res_0 = temp; res_1 = seq[res_1]>seq[i]?i:res_1;}
            }else
            if(i==r){
                int[] VandN = dp(l,i-1);
                int temp = VandN[0] + seq[i]*seq[VandN[1]];
                if(temp <= res_0) {res_0 = temp; res_1 = seq[res_1]>seq[i]?i:res_1;}
            }else{
                int[] lVandN = dp(l,i-1);
                int[] rVandN = dp(i+1,r);
                int temp = lVandN[0] + seq[i]*seq[lVandN[1]] + seq[i]*seq[rVandN[1]] + rVandN[0];
                if(temp <= res_0) {res_0 = temp; res_1 = seq[res_1]>seq[i]?i:res_1;}
            }
        }
        return new int[]{res_0,res_1};
    }
}