Loading [MathJax]/jax/output/HTML-CSS/jax.js
0%

LeetCode 823. Binary Trees With Factors

题目

原题在此

解析

dp[i]=ij=0j{arr[j]|arr[i]modarr[j]==0},dp[arr[i]/arr[j]]dp[arr[j]]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
};