东莞住房和城乡建设局网站,温岭市建设局网站,如何创建一个论坛网站,货运配载做网站文章目录1. 题目2. 解题2.1 DP2.2 单调栈贪心1. 题目
给你一个正整数数组 arr#xff0c;考虑所有满足以下条件的二叉树#xff1a;
每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。#xff08;知识回顾#xff1a;如果一个…
文章目录1. 题目2. 解题2.1 DP2.2 单调栈贪心1. 题目
给你一个正整数数组 arr考虑所有满足以下条件的二叉树
每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。知识回顾如果一个节点有 0 个子节点那么该节点为叶节点。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中返回每个非叶节点的值的最小可能总和。 这个和的值是一个 32 位整数。
示例
输入arr [6,2,4]
输出32
解释
有两种可能的树
第一种的非叶节点的总和为 36
第二种非叶节点的总和为 32。24 24/ \ / \12 4 6 8/ \ / \
6 2 2 4提示
2 arr.length 40
1 arr[i] 15
答案保证是一个 32 位带符号整数即小于 2^31。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 DP
类似题目 LeetCode 1039. 多边形三角剖分的最低得分区间DP
区间DP见注释
class Solution {
public:int mctFromLeafValues(vectorint arr) {int n arr.size();vectorvectorpairint, int dp(n, vectorpairint, int(n, {INT_MAX, 0}));//dp[i][j] 表示区间 [i,j] 的 {非叶节点的min(sum), 区间的最大叶子节点值}for(int i 0; i n; i) //初始化{dp[i][i].first 0;//sumdp[i][i].second arr[i];//maxval}for(int len 1; len n; len)//区间长度{for(int i 0, j; ilen n; i)//左端点{j ilen;//右端点for(int k i; k j; k)//枚举中间端点{if(dp[i][j].first dp[i][k].firstdp[k1][j].firstdp[i][k].second*dp[k1][j].second){ //左区间的和 右区间的和 当前节点的val maxL*maxRdp[i][j].first dp[i][k].firstdp[k1][j].firstdp[i][k].second*dp[k1][j].second;//用更小的sum更新dp[i][j].second max(dp[i][k].second, dp[k1][j].second);// 更新区间的最大叶节点值}}}}return dp[0][n-1].first;}
};16 ms 9.3 MB
2.2 单调栈贪心
维护单调递减栈让一个数字跟其相邻的2个数字中的较小的相乘
class Solution {
public:int mctFromLeafValues(vectorint arr) {int n arr.size(), tp, ans 0;stackint stk;stk.push(INT_MAX);for(int a : arr){while(a stk.top())//单调递减栈不满足了弹栈{tp stk.top();stk.pop();ans tp*min(a, stk.top());}stk.push(a);}while(stk.size() 2){tp stk.top();stk.pop();ans tp*stk.top();}return ans;}
};0 ms 8.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步