[leetcode] 1130. Minimum Cost Tree From Leaf Values

[leetcode] 1130. Minimum Cost Tree From Leaf Values

Description

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:

Input: arr = [6,2,4]Output: 32Explanation:There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32. 24 24 / \ / \ 12 4 6 8 / \ / \6 2 2 4

Constraints:

2 <= arr.length <= 401 <= arr[i] <= 15It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

分析

题目的意思是：求出由叶子节点构造二叉树的最小代价，其中非叶子结点的值为子树最大叶子结点的乘积。这道题看上去是二叉树的问题，实际上是动态规划的问题。 dp[i][j]表示叶子结点从i…j的最小代价，因此递推公式可以是：

dp(i, j) = min(dp(i, j), largest(i, k) * largest(k + 1, j) + dp(i, k) + dp(k + 1, j)

largest[i][j]存放的是i…j的最大叶子结点 整个递推公式表示的是i…j叶子结点构成的最小二叉树=i…k构成的左最小二叉树+k+1…j构成的最小右二叉树+当前结点的最大值。 时间复杂度为O(n^3)

代码

class Solution: def mctFromLeafValues(self, arr: List[int]) -> int: MAX_INT=sys.maxsize n=len(arr) dp=[[0]*n for i in range(n)] large=[[0]*n for i in range(n)] for i in range(n): large[i][i]=arr[i] for j in range(i+1,n): large[i][j]=max(large[i][j-1],arr[j]) for d in range(1,n): for i in range(0,n-d): j=i+d dp[i][j]=MAX_INT for k in range(i,j): dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+large[i][k]*large[k+1][j]) return dp[0][n-1]

参考文献

​​[LeetCode] Leetcode 1130 Minimum Cost Tree From Leaf Values​​​​[LeetCode] LeetCode 刷题 1130 Minimum Cost Tree From Leaf Values​​​​[Leetcode]LeetCode 1130. Minimum Cost Tree From Leaf Values ​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。