最优二叉树||

import java.io.*;
public class Main{
    //每个节点选择对应的开销   
    static int[][][] mem;
    static int[] weight;
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());
        String[] str = br.readLine().split(" ");
        weight = new int[n];
        for(int i = 0; i < n; i++){
            weight[i] = Integer.parseInt(str[i]);
        }
        //mem[l][r][k]表示以weight[l:r]为子节点，以weight[k]为根节点的树开
        mem = new int[n][n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    mem[i][j][k] = -1;
                }
            }
        }
        System.out.println(recur(0, n - 1, -1));
    }

    public static int recur(int left, int right, int root){

        if(left > right) return 0;
        //左右子树和根节点这个结构已经被记录过的情况下，直接返回，减少搜索时间
        if(root >= 0 && mem[left][right][root] != -1) return mem[left][right][root];
        int cost = Integer.MAX_VALUE;
        int leftCost = 0, rightCost = 0;
        //在这个数组中按照中序遍历的格式去寻找
        for(int i = left; i <= right; i++){
            //递归下去 每次都会在区间寻找开销比较小的左右子树
            leftCost = recur(left, i - 1, i);
            rightCost = recur(i + 1, right, i);
            cost = Math.min(cost, leftCost + rightCost + weight[i] * (root != -1 ? weight[root] : 0));
        }
        //记录
        if(root >= 0) mem[left][right][root] = cost;
        return cost;
    }
}

有三点值得学习：

• 采用输入流来接收，比较方便
• 采用备忘录数组，来记录每个选择结构节点的开销，减少了递归搜索的时间，直接返回结果，也需要在这个递归中记录结果
• 全程使用数组去模拟二叉树，采用分治思想，去递归