一道有趣的binary tree问题

最近在刷题的时候见到了这个题，想问一下大致的思路或者做法：


我的理解是这样的

1. 首先算最大树深：max n that 2 ** (n-1) < len(array) < 2 ** n

2. 依次搭建（循环？）子树

3. 计算所有nodes的和

但是不知道对不对。。。。求高人指点！

xliu34 发表于 2019-2-12 09:29
Each node has 0 or 2 children, so the formula is 2 each steps?

这个题目有个注意点是arr的元素都是叶子结点，所以任意长度>=1的子数组都可以构成合法的subtree，不需要step=2

其实题目给的样例就已经很明确啦，arr中有3个元素[4, 6, 2]，那么计算过程是

MinCost(0, 2) = min{ MinCost(0, 0) + MinCost(1, 2) + MaxElem(0, 0) * MaxElem(1, 2),
                               MinCost(0, 1) + MinCost(2, 2) + MaxElem(0, 1) * MaxElem(2, 2) }
--
                    = min{ 0 + arr[1] * arr[2] + arr[0] * max(arr[1], arr[2]),
                               arr[0] * arr[1] + 0 + max(arr[0], arr[1]) * arr[2] }
--
                    = min{ 0 + 6 * 2 + 4 * max(6, 2),
                               4 * 6 + 0 + max(4, 6) * 2 }
--
                    = min{ 12 + 24, 24 + 12 } = 36


上述每一步min中的两个表达式正好对应于样例里画出来的两个树结构，注意到枚举时的step是1

其实说是tree的题 不如说是array的题.    如果array是偶数长度 那么只有一种分法 你直接计算

如果array是奇数长度 那么也就只有两种分法. 要么index0单独  要么index最后一个单独

分别计算求最小

我之前做OA也遇到这个题 时间到了也没一个清晰的思路... 同求高人指点

为什么我觉得是个DP... 数列an
设g(n)为前n个中最大的值, f(n)为前n个最小的cost
f(n) = min( f(n-2) + g(n-2)* max(a_(n-1), a_n) + a_(n-1) * a_n, f(n - 1) + g(n-1) * an )
f(1) = 0 f(2) = a1 * a2

补充内容 (2019-2-7 08:41):
hmmm 不对

感谢大家的回复！

现在变成了一个dp或者迭代，我给出我的一点点思路（过不了编译器）

1. def costCalculator(array):
   
2.     max_depth = len(bin(len(array) -1)) - 2
   
3.     if len(array) % 2 == 1 and len(array) > 2:
   
4.         return (array[0] + 1) * costCalculator(array[1:])
   
5.    
   
6.     elif len(array) == 1:
   
7.         return 1
   
8.    
   
9.     else:
   
10.         if len(array) == 2:
    
11.             return(array[0] * array[1])
    
12.         else:
    
13.             if max_depth > 1:
    
14.                 return min(array[:2**(max_depth - 1)]) * min(array[2**(max_depth -1):]) + costCalculator(array[:2**(max_depth - 1)]) + costCalculator(array[2**(max_depth -1):])

复制代码

zhangzitong001 发表于 2019-2-6 20:49
其实说是tree的题 不如说是array的题.    如果array是偶数长度 那么只有一种分法 你直接计算

如果array是 ...

能再解释一下行吗？
e.g., array 2 4 5 6 8 10 12 100
can split into 24 56 810 12100 cost 2942
or can split into 4 layers, cost 2402 (8+30+24+80+60+1200+1000, root 1000)

                     12+100
           8+10
24 56

可以用DP在O(n^3)时间解决

首先定义：
--
(1) MaxElem(I, J) = 子数组 arr[I] ... arr[J] 中最大元素的值
--
(2) MinCost(I, J) = 用子数组 arr[I] ... arr[J] 建立一个满足要求的subtree所需的最小cost
--
那么MinCost(0, len(arr) -1)就是题目要求的最终结果


现在考虑怎么计算MaxElem和MinCost

首先MaxElem可以用O(n^2)时间预先计算出来并保存为一个二维数组

MinCost根据题目的定义容易写出
--
递归表达式（状态转移方程）：MinCost(I, J) = min{ MinCost(I, K) + MinCost(K+1, J) + MaxElem(I, K) * MaxElem(K+1, J) | K = I ... J - 1 }
--
边界条件：MinCost(I, I) = 0
--

根据递归表达式用三个for循环I, J, K就可以自底向上的计算MinCost了，或者也可以用递归+memo的方法

magicsets 发表于 2019-2-11 10:40
可以用DP在O(n^3)时间解决

首先定义：

Each node has 0 or 2 children, so the formula is 2 each steps?

先谢谢您，下班再推您的公式