数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python实现最小成本叶值树
假设我们有一个正整数数组arr，考虑所有满足以下条件的二叉树：
- 每个节点要么有0个子节点，要么有2个子节点；
- 数组arr的值对应于树的中序遍历中每个叶子的值。
- 每个非叶子节点的值等于其左右子树中最大叶节点值的乘积。
在所有可能的二叉树中，我们必须找到每个非叶子节点值可能的最小总和。例如，如果输入arr为[6,2,4]，则输出为32，因为可能有两种树：
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为memo的映射
- 定义一个名为dp()的方法，它将i和j作为参数。它的工作原理如下：
- 如果j <= i，则返回0
- 如果(i, j)在memo中，则返回memo[(i, j)]
- res := 无穷大
- 对于k从i到j – 1的范围
- res := res，dp(i, k) + dp(k + 1, j) + (arr从索引i到k + 1子数组的最大值) * (arr从k + 1到j + 1子数组的最大值)的最小值
- memo[(i, j)] := res
- 返回memo[(i, j)]
- 主方法将调用此dp()方法，方法如下：调用dp(0, arr的长度 - 1)
让我们来看下面的实现来更好地理解：
示例
class Solution(object):
def mctFromLeafValues(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
self. memo = {}
def dp(i,j):
if j<=i:
return 0
if (i,j) in self.memo:
return self.memo[(i,j)]
res = float('inf')
for k in range(i,j):
res = min(res,dp(i,k) + dp(k+1,j) + (max(arr[i:k+1])*max(arr[k+1:j+1])))
self.memo[(i,j)]=res
return self.memo[(i,j)]
return dp(0,len(arr)-1)输入
[6,2,4]
输出
32
更新于：2020年3月5日
382 次浏览
广告