首页 > 试题广场 >

最优二叉树

[编程题]最优二叉树

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

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

输入描述:

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

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

输出描述:

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

示例1

输入

5
7 6 5 1 3

输出

说明


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

算法知识视频讲解

pein531

与第十场试卷的第四题“最优二叉树II”的思路相同，分治重构二叉树+记忆化搜索。用mem[left][right]表示利用节点weight[left: right]构建子树的最小开销。而深度，我们可以利用一个技巧来考虑：

首先任然是通过遍历，让left~right的每一个节点都当一次根节点；然后从根节点处将数组分为左右两个部分再分别构建左右子树。我们可以这样考虑，对于每一层递归，都将这一层构建子树的所有节点的权值都求一次和，每向下递归一层就累加一遍构建子树的节点权值，这样越深的节点就加得越多，对于第 i 层的节点，其权重就加了 i 次，相当于考虑了深度。而每次根节点处于相对的第0层，所以每层计算节点权重之和时要记得减去根节点的权重。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    static int[][] mem;
    static int[] weight;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        mem = new int[n][n];
        for(int i = 0; i < n; i++)
            Arrays.fill(mem[i], -1);
        String[] strW = br.readLine().trim().split(" ");
        br.close();
        weight = new int[n];
        for(int i = 0; i < n; i++)
            weight[i] = Integer.parseInt(strW[i]);
        // 从第0层开始
        System.out.println(recur(0, n - 1));
    }
    
    // 计算用[left,right]的元素构建子树的最小开销
    private static int recur(int left, int right) {
        // 无法构成子树，返回0开销
        if(left >= right)
            return 0;
        // 该子树的最小开销已经计算过，直接返回
        if(mem[left][right] != -1)
            return mem[left][right];
        int rawWeightSum = 0;
        // 首先，每个节点都要加上其本身的权重
        for(int i = left; i <= right; i++)
            rawWeightSum += weight[i];
        int cost = Integer.MAX_VALUE;
        // 穷举根节点，继续向下构建子树，每向下构建一次子树，就会把子树节点的权重再加一次，相当于考虑了深度
        for(int i = left; i <= right; i++){
            // 左子树权值+右子树权值+全部节点权值-根节点权值
            cost = Math.min(cost, recur(left, i - 1) + recur(i + 1, right) + rawWeightSum - weight[i]);
        }
        mem[left][right] = cost;
        return cost;
    }
}

编辑于 2021-03-13 22:27:41 回复(0)

乔乔201909151609884

#include<bits/stdc++.h>
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int>t(301,0);
    vector<vector<int>>dp(301,vector<int>(301,0));
    for(int i=0;i<n;i++)
        cin>> t[i];
    for(int j=0;j<=n-1;j++)
    {
        for(int i=0;i+j<n;i++)    //[i,i+j]
        {
            int all=0;
            for(int k=i;k<=i+j;k++)
                all += t[k];
            int minc=INT_MAX;    
            for(int k=i;k<=i+j;k++)
            {
                minc=min(minc,dp[i][k-1]+dp[k+1][i+j]+all-t[k]);
            }
            dp[i][i+j]=minc;
        }
    }
    cout<<dp[0][n-1]<<'\n';
    return 0;
}

编辑于 2023-06-26 11:44:43 回复(0)

Python

顺利上岸吧求求了

每个数分别作为根节点，那么在左右子树当中一定是最大的数当作左右子树的根节点，这样保持距离最小（按照他的例子是对的）。但实际只过了两个例子，特殊情况什么样就不知道了

from collections import deque
n=int(input())
w=list(map(int, input().strip().split()))
class tree:
    def __init__(self, val=0, left=None, right=None):
        self.left=left
        self.right=right
        self.val=val
def process(nums):
    if not nums: return
    num=max(nums)
    idx=nums.index(num)
    root=tree(num)
    root.left=process(nums[:idx])
    root.right=process(nums[idx+1:])
    return root
def pro(root):
    if not root: return 0
    res=root.val
    res+=pro(root.left)+pro(root.right)
    return res
min_res=float('inf')
extra=sum(w)
for i in range(len(w)):
    root=tree(w[i])
    root.left=process(w[:i])
    root.right=process(w[i+1:])
    que=deque([root])
    res=0
    while que:
        node=que.popleft()
        res+=pro(node)
        if node.left: que.append(node.left)
        if node.right: que.append(node.right)
    min_res=min(min_res, res-extra)
print(min_res)

发表于 2022-03-29 17:01:01 回复(0)

牛客843191783号

//C++ dp树实现，思路细节请看楼上大佬的Java注解。
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int ve[310];
int dp[310][310];
int f(int l, int r, int level) {
	if (l > r) { return 0; }
	if (dp[l][r]!=-1) { return dp[l][r]; }
	int ret = 2e9, all = 0;
	for (int i = l; i <= r; i++) { all += ve[i]; }
	for (int i = l; i <= r; i++) {
		int left = f(l, i - 1, level+1);
		int right = f(i + 1, r, level+1);
		ret = min(ret, left + right + all - ve[i]);
	}
	dp[l][r] = ret;
	return ret;
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> ve[i]; }
	memset(dp, -1, sizeof dp);
	f(0, n - 1, 0);
	cout << dp[0][n-1] << endl;
	return 0;
}

编辑于 2021-09-15 16:53:52 回复(0)

JCoder

区间 DP

假设现在有一颗根是 x 的二叉树 T ，那么将点root 作为 x 的父节点所得到的二叉树 T' 的权值就是整棵树 T 的权值和加上 T 中所有点的点权和，注意后者是点权和，不是整体的权值和。

利用这个特性，求一个前缀和，然后就可以进行区间 DP 了

我的代码中认为根节点的深度是 1，题目中的设计是 0，所以最后减去了整棵树的点权和。

#include <bits/stdc++.h>
using namespace std;

int n, a[305], dp[305][305];
int pre_a[305];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    pre_a[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre_a[i] = pre_a[i - 1] + a[i - 1];
    }

    memset(dp, 0x3f3f3f3f, sizeof dp);
    for (int i = 0; i < n; i++) {
        dp[i][i] = a[i];
        dp[i][i - 1] = 0;
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            for (int k = i; k <= j; k++) {
                int left = 0, right = 0;
                if (k != i) {
                    left = dp[i][k - 1] + pre_a[k] - pre_a[i];
                }
                if (k != j) {
                    right = dp[k + 1][j] + pre_a[j + 1] - pre_a[k + 1];
                }
                dp[i][j] = min(dp[i][j], left + right + a[k]);
            }
        }
    }
    printf("%d\n", dp[0][n - 1] - pre_a[n]);

    return 0;
}

发表于 2021-08-18 19:46:52 回复(0)