题目地址：https://leetcode.com/problems/binary-trees-with-factors/description/
题目描述
Given an array of unique integers, each integer is strictly greater than 1.
Wemake a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node's value should be equal to the product of the values of it's children.
Howmany binary trees can we make? Return the answer modulo 10 ** 9 + 7.
Example 1:
Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:
Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
Note:
1、 1<=A.length<=1000.；
2、 2<=A[i]<=10^9.；
题目大意
给定了一个数组，可以从这个数组中选取任意多的节点构建成二叉树，要求二叉树中的非叶子节点的值必须等于其子节点的和。问有多少种组合方案。
解题方法
动态规划
题目出现了DP的最最明显提示：需要对结果求模！这个说明结果很大，必须通过DP求解了。
方法其实很简单的，首先需要先排序，注意到题目中说了数组是Unique的，所以每个数字出现的次数只有1次。使用dp数组保存每个数字作为根节点的情况下能构建出的所有二叉树数目，求法是遍历所有小于自己的数字取值作为左子树，然后把根节点/左子树的值当做右节点，然后对他们能组成的二叉树数目乘积求和。
dp[i] = sum(dp[j] * dp[i / j])
res = sum(dp[i])
需要注意的是，一定要保证根节点/左子树的结果是整数，而且也在dp内，才去做状态转移。因为，题目给的每个数字都是大于1的，因此根节点/左子树一定小于根节点，所以直接判断它是否在dp里出现过就行了，它不可能在更后面才出现。
时间复杂度是O(NlogN + N)，空间复杂度是O(N).
class Solution(object):
def numFactoredBinaryTrees(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
dp = {}
for i, a in enumerate(A):
dp[a] = 1
for j in range(i):
if a % A[j] == 0 and a / A[j] in dp:
dp[a] += dp[A[j]] * dp[a / A[j]]
return sum(dp.values()) % (10**9 + 7)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发