首页 > 试题广场 >

最优二叉树II

[编程题]最优二叉树II

热度指数：7375 时间限制：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。

算法知识视频讲解

JavaScript

一只小塔姆

美团不当人系列...妥妥的hard 二叉树+dp, 还是三维dp, 树还要考虑虚拟节点, 而且树有三层结构parent==>root==>left+right

const readline=require('readline');
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
const arr=[];
rl.on('line',function(line){
    arr.push(line);
    if(arr.length===2){
        let len=Number(arr[0]);
        let w=arr[1].split(' ').map(Number);
        w.unshift(0);

        //1.dp[low][high][root]表示以root为根节点,
        //其左/右子树节点范围在data[low,high]内的最小开销(左或者右,只有一边)
        //2.len+1是因为需要有一个虚拟的根节点
        let dp=Array.from({length:len+1},
            ()=>Array.from({length:len+1},()=>Array(len+1).fill(-1)));
        const dfs=(low,high,root)=>{
            if(low>high) return 0;
            //如果访问过则直接返回
            if(dp[low][high][root]!=-1) return dp[low][high][root];
            //在low~high每个位置都有可能作为根节点
            let cost=Infinity;
            for(let i=low;i<=high;i++){
                let left=dfs(low,i-1,i);
                let right=dfs(i+1,high,i);
                cost=Math.min(cost,left+right+w[i]*w[root]);
            }
            return dp[low][high][root]=cost;
        }
        console.log(dfs(1,len,0));

        //next
        arr.length=0;
    }
})

发表于 2021-04-06 15:44:16 回复(0)