LeetCode 823. Binary Trees With Factors

题目

原题在此

解析

$dp[i] = \sum_{j=0}^i \forall{j} \{arr[j] | arr[i] \mod arr[j] == 0\}, dp[arr[i]/arr[j]] * dp[arr[j]]$

代码

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        long res = 0, m = 1e9+7;
        sort(arr.begin(), arr.end());
        unordered_map<int, long> dp;
        for(int i = 0; i < arr.size(); ++i) {
            dp[arr[i]] = 1;
            for(int j = 0; j < i; ++j) {
                if(arr[i] % arr[j] == 0) {
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] / arr[j]]) % m;
                }
            }
            res = (res + dp[arr[i]]);
        }
        return res % m;
    }
};