题目
原题在此
解析
$dp[i] = \sum_{j=0}^i \forall{j} \{arr[j] | arr[i] \mod arr[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;
}
};
|