https://leetcode.com/problems/binary-trees-with-factors/description/
823. Binary Trees With Factors
给你一个阵列 arr,里面的数字不重复且大于 1,我们可以不限制次数的使用这些
数字构建出一个二元树,这个二元树需要满足左右节点的值相乘等于父节点,求出
共有几种组合。
Example 1:
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
思路:
1.动态规划,如果 arr[i] = arr[j] * arr[k] 则他可以组成一个三个节点的二元树
假设 dp(n) 表示这个数字共有几种组合,每个数字都当根节点的话至少有一种组合,
所以我们把每个数字的组合初始化为 1。
2.我们可以先把 arr 从小到大排序,这样只需要检查比 i 小的 arr[j] 是否存在因子
arr[k](检查所有索引小于 i 的 arr),如果存在的话可以构建出
dp(arr[j]) * dp(arr[k]) 种树,把他累加到 dp(arr[i]),因为我们排序过的关系,
所以处理到 i 的时候,dp(arr[j]) 和 dp(arr[k]) 一定已经计算完。
3.最后把 dp(arr[0], ....arr[n - 1]) 加总就是答案,因为数字很大所以要模 1e9+7。
Java Code: