# 0823. Binary Trees With Factors
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/binary-trees-with-factors/description/
## 思路
基本型II
记录每个数字能生成多少个binary tree
当遇到新的数字```num```时 检查前面每一个数字```prev``` 看```num```能不能整除```prev``` 以及```num/prev```在不在map里面 如果两种情况都成立 那么就可以由这两个数字构成```map[prev]*map[num/prev]```种binary tree
## Code

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        dp = dict()
        arr.sort()
        ans = 0
        for i, num in enumerate(arr):
            currNumOfTrees = 1
            for prevNum in arr[0:i]:
                if num%prevNum==0 and num//prevNum in dp:
                    currNumOfTrees += dp[num//prevNum]*dp[prevNum]
            dp[num] = currNumOfTrees
            ans += dp[num]
            ans %= 1e9+7
        return int(ans)