首页 > 试题广场 >

最优二叉树II

[编程题]最优二叉树II

热度指数：7401 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。

输入描述:

第一行输入一个整数N（1<=N<=300），表示二叉树的节点数。

第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。

输出描述:

输出一个整数，表示最优二叉树的总开销。

示例1

输入

5
7 6 5 1 3

输出

说明


最优二叉树如图所示，总开销为7*1+6*5+5*1+1*3=45。

算法知识视频讲解

Java

Errerless

树形 dp，第三个维度大小为 2 即可：

0 表示当前 i-j 是上一层的左子树，根节点为 j + 1；

1 表示当前 i-j 是上一层的右子树，根节点为 i - 1

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        int[][][] f = new int[n + 2][n + 2][2];
        for (int i = n; i >= 1; i--) {
            f[i][i][0] = a[i] * a[i + 1];
            f[i][i][1] = a[i] * a[i - 1];
            for (int j = i + 1; j <= n; j++) {
                f[i][j][0] = Integer.MAX_VALUE;
                f[i][j][1] = Integer.MAX_VALUE; 
                for (int k = i; k <= j; k++) {
                    f[i][j][0] = Math.min(f[i][j][0], a[k] * a[j + 1] + f[i][k - 1][0] + f[k + 1][j][1]);
                    f[i][j][1] = Math.min(f[i][j][1], a[k] * a[i - 1] + f[i][k - 1][0] + f[k + 1][j][1]);
                }
            }
        }
        System.out.println(f[1][n][0]);
    }
}

编辑于 2024-03-01 13:23:08 回复(0)

Java

lemonjz

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n + 1];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            Main main = new Main();
            int ans = Integer.MAX_VALUE;
            int[][][] memo = new int[n + 1][n + 1][n + 1];
            for (int i = 0; i < n; i++) {
                ans = Math.min(ans,main.dfs(nums,0,i - 1,i,memo) + main.dfs(nums,i + 1,n - 1,i,memo));
            }
            System.out.println(ans);
        }
    }
    int dfs(int[] nums, int l, int r, int father, int[][][] memo) {
        if (l > r) return 0;
        if (l == r) return nums[l] * nums[father];
        if (memo[l][r][father] != 0) return memo[l][r][father];
        int res = Integer.MAX_VALUE;
        for (int i = l; i <= r; i++) {
            int left = dfs(nums, l, i - 1, i, memo);
            int right = dfs(nums, i + 1, r, i, memo);
            res = Math.min(res, left + right + nums[i] * nums[father]);
        }
        memo[l][r][father] = res;
        return res;
    }
}

编辑于 2021-03-23 14:40:52 回复(1)