823. Binary Trees With Factors 带因子的二叉树

@TOC

# 题目描述

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

# 解题方法

# 动态规划

``````dp[i] = sum(dp[j] * dp[i / j])
res = sum(dp[i])
``````

``````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)
``````

# 参考资料

https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C++JavaPython-DP-solution

# 日期

2018 年 10 月 30 日 —— 啊，十月过完了