题目
原题在此
解析
dp[i]=∑ij=0∀j{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; } };
|