首页 > 试题广场 >

最优二叉树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

输出

45

说明

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

算法知识视频讲解
开通博客
头像 皮蛋秀柚秋
发表于 2021-02-28 15:41:35
如图，该题是美团2021春招笔试题。当时做卷子想复杂了，觉着一个中序序列构建的树有多种可能，每种可能都得计算出开销，同时记录下最小开销。直接爆炸。后来看题解才觉悟是一个经典的分治问题 #include<bits/stdc++.h> using namespace std; const i 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 zhangzx123
发表于 2022-11-26 00:07:33
区间dp： dp[l][r][0]表示区间l~r作为左子树的最小开销 dp[l][r][1]表示区间l~r作为右子树的最小开销 对于区间[l][r]枚举根节点k，分别计算l~r作为左子树和作为右子树的最小代价 在l~r区间上，以k为根的树作为左子树的代价可以计算为val[k]*val[r+1]+dp 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 大厂算法岗必拿下
发表于 2021-09-22 08:15:32
树形DP。 备忘录减少算法复杂度（-1）说明没有访问过。里面保存的就是最小，所以直接用就行 father这个假节点很重要。 #include<bits/stdc++.h> using namespace std; const int maxN = 301; vector<int& 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
26条回答 20283浏览

热门推荐

通过挑战的用户

相关试题

最优二叉树II

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号