823. Binary Trees With Factors

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

Python

Bottom Up DP

• Offical solution

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        arr.sort()

        dp = [1] * len(arr)
        mapper = {num: index for index, num in enumerate(arr)}

        for i, num in enumerate(arr):
            for j in range(i):
                left, right = num % arr[j], num / arr[j]
                if left == 0 and right in mapper:
                    dp[i] += dp[j] * dp[mapper[right]]
                    dp[i] %= (10**9+7)

        return sum(dp) % (10**9+7)