题目描述：

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.

题目大意：

给定一组互不重复的正整数。

利用正整数构建二叉树，每一个非叶子节点都必须等于其子节点的乘积。

求可以构建多少种不同的二叉树。

解题思路：

动态规划（Dynamic Programming）

将A从小到大排序

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

其中，m * n == a 并且a % m == 0，m <= sqrt(a)

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

 

本文链接：http://bookshadow.com/weblog/2018/04/22/leetcode-binary-trees-with-factors/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码