Problem

题目大意：给你一些可以重复使用的数字问能够构成多少种不同的特殊二叉树（根结点的值需为子节点值的乘积）。

https://leetcode.com/problems/binary-trees-with-factors/description/

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.

Solution: DP

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].

dp[i] = sum(dp[j] * dp[i/j]),  0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.

      A[i]
     /    \
 A[j]  (A[i]/A[j])
  / \     / \
 .....   .....

ans = sum(dp[i]), for all possible i.

Time complexity: O(n^2)

Space complexity: O(n^2)

C++