题目描述
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。
示例 1:
- 输入:
arr = [2, 4]
- 输出: 3
- 解释: 可以得到这些二叉树:
[2], [4], [4, 2, 2]
示例 2:
- 输入:
arr = [2, 4, 5, 10]
- 输出:
7
- 解释: 可以得到这些二叉树:
[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示：
1 <= arr.length <= 1000- 2 <= arr[i] <= 109
arr 中的所有值 互不相同
解法一：动态规划 + 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
func numFactoredBinaryTrees(arr []int) int {
n := len(arr)
const Mod = int64(1e9 + 7)
sort.Ints(arr)
dp, ans := make([]int64, n), int64(1)
dp[0] = 1
for i := 1; i < n; i++ {
left, right := 0, i-1
dp[i] = 1
for left <= right {
product := int64(arr[left]) * int64(arr[right])
if product == int64(arr[i]) {
if left == right {
dp[i] = (dp[i] + dp[left]*dp[right]) % Mod
} else {
dp[i] = (dp[i] + dp[left]*dp[right]*2) % Mod
}
left++
right--
} else if product > int64(arr[i]) {
right--
} else {
left++
}
}
ans = (ans + dp[i]) % Mod
}
return int(ans)
}
|
