Detailed Explanation With Example and Code | C++ | DP
Let\'s say that A is a number that can be represented as\n\nA = B * C \nA = D * D\nA = C * B\n\nand The array arr[] contains all the numbers A,B,C, and D.  Now 
Let\'s say that **A** is a number that can be represented as\n\n**A = B * C** \n**A = D * D**\n**A = C * B**\n\nand The array **arr[]** contains all the numbers A,B,C, and D.  Now ,\n\n**N(A)** = Number of binary trees which has root node A\n**N(B)** = Number of binary trees which has root node B\n**N(C)** = Number of binary trees which has root node C\n**N(D)** = Number of binary trees which has root node D\n**N(T)** = Total Number of Nodes\n\n***N(A) = ( N(B)  N(C) )  + ( N(D)  N(D) )  +  ( N(C)  N(B) ) + 1 .  .... (1)***\n\n**N(B) * N(C)** now equals **N(C) * N(B)**. Therefore, the only thing we can do is multiply N(B) * N(C) by 2 .\xA0 Equation (1) can therefore be expressed as\n\n***N(A) = ( N(B)  N(C) )  2  + ( N(D)  N(D) )  + 1 .  .... (2)***\n\n* If the left and right nodes are not the same, we can state that their product will be multiplied by two and added to the result.\n* If the left and right nodes are not the same, we can state that their product will be multiplied by one and added to the result.\n* 1 will be added to the answer because every node itself is a tree with one node only. \n\nTotal number of Nodes will be \n**N(T) = N(A) + N(B) + N(C) + N(D)** \n\n\nLet us apply the above formula for arr = [ 2, 4 , 8 , 16 ]\n\n* **2** : we will get only one binary tree  so , N(2) = 1  \n* **4** :  4 = 2 * 2 .  As we know N(2) = 1  and here both the factors are same so we will multiply their product by 1 and add to the answer .  so, N(4) = ( N(2) * N(2) ) * 1 + 1 = (1 * 1) * 1 + 1 = 2 \n* **8**:  8 = 2 * 4 .  as we know N(4) = 2 , N(2) = 1 and here both the factors are different so we will multiply their product by 2 and add to the answer. so, N(8) = ( (N(2) * N(4) ) * 2 + 1 = 5 .  now 8 can be also written as 8 = 4 * 2 . However, as we previously stated, we would only select one combination between (2, 4) and (4, 2), thus we multiplied the product of N(2) and N(4) by 2.  \n* **16**: 16 = 4 * 4 and 16 = 2 * 8 . so we can say , N(16) = N(4) * N(4) * 1 + N(2) * N ( 8) * 2 + 1 = 2 * 2 * 1 + 5 * 1 * 2 + 1 = 15 . \n\nHere are the trees which have 2,4 and 8 as their root node respectively ,\n\n![image](https://assets.leetcode.com/users/images/d6ff0304-571c-4f24-9051-8f2c59873316_1660044028.5125227.png)\nnow **N(T) = N(16) + N(8) + N(4) + N(2) = 15 + 5 + 2 + 1 = 23**\n\nRecursive DP Solution : \n\n```\nclass Solution {\npublic:\n    map<int,int> factor;\n    int MOD = 1e9 + 7 ;\n    void setUp(vector<int>& arr) {\n        for ( int i = 0 ; i < arr.size() ; i++) factor[arr[i]] = i+1 ;\n    }\n\n    int solution(vector<int>& arr, vector<int>& dp, int index) {\n        if ( index < 0) return 0 ;\n        if ( dp[index] != -1) return dp[index];\n        dp[index] = 1 ;\n        for ( int i = 2 ; i*i <= arr[index] ; i++ ) {\n            if ( arr[index] % i == 0 && factor[i] && factor[arr[index]/i]) {\n                long long way1 = solution(arr,dp,factor[i]-1)%MOD;\n                long long way2 = solution(arr,dp,factor[arr[index]/i]-1)%MOD;\n                long long prod = (way1*way2)%MOD ;\n                if ( i == arr[index]/i) dp[index] += prod;\n                else dp[index] += ((2*prod)%MOD) ;\n                dp[index] = dp[index]%MOD;\n            }\n        }\n        return dp[index]%MOD;\n    }\n    \n    int numFactoredBinaryTrees(vector<int>& arr) {\n        sort(arr.begin(),arr.end());\n        setUp(arr);\n        vector <int> dp (arr.size()+2,-1);\n        long long ans = 0 ;\n        for ( int i = arr.size()-1 ; i >= 0 ; i-- ) ans += ((solution(arr,dp,i)%MOD)%MOD) ;   \n        return ans%MOD ;\n    }\n};\n```\nNow let me explain some of lines of my code : \n\n* Suppose A = B * C and A = C * B ( Here, B < C ) line below will take only the pair B * C in count . \n  \n  ```\n       for ( int i = 2 ; i*i <= arr[index] ; i++ )\n  ```\n*  Suppose A = D * D then we will mutiply N(D) * N (D) by 1 and if A = B * C then we will multiply N(B) * N(C) by 2 .\n    ```\n        if ( i == arr[index]/i) dp[index] += prod;\n        else dp[index] += ((2*prod)%MOD) ;\n    ```\n\n*  Every Node itself is a binary tree .\n    ```\n        dp[index] = 1 \n   ```\n\n*  Let Us check if both the factors are presented in the array arr[] with the help of map which we constructed  . \n   ```\n      if ( arr[index] % i == 0 && factor[i] && factor[arr[index]/i])\n   ```\n\n
['Dynamic Programming', 'Tree']