题目描述：

LeetCode 823. Binary Trees With Factors

Given an array of unique integers, each integer is strictly greater than 1.

We make 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.

How many 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`.

解题思路：

```将A从小到大排序

dp[a] = sum(dp[m] * dp[n] * (1 + (m != n))) % MOD

Python代码：

``````class Solution(object):
def numFactoredBinaryTrees(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
dp = collections.defaultdict(int)
MOD = 10 ** 9 + 7
for i, a in enumerate(A):
num = 0
for j in range(i):
m = A[j]
if m * m > a: break
if a % m: continue
n = a / m
num = (num + dp[m] * dp[n] * (1 + (m != n))) % MOD
dp[a] = num + 1
return sum(dp.values()) % MOD
``````

Pingbacks已关闭。