DP | Rec -> Memo -> Tabul | C++
So let\'s underestand the problem,\nInput: 2, 5, 6, 10, 4, 3\nOutput: 11\n\nThat means by using these numbers we can create 11 unique binary trees by following 
So let\'s underestand the problem,\nInput: 2, 5, 6, 10, 4, 3\nOutput: 11\n\nThat means by using these numbers we can create 11 unique binary trees by following the rule,\n**root_val = left_child_val * right_child_val**\n\nFrom this, we can get the left and right values that need to be less than the root. So to efficiently check on fewer values we can sort the array so that all the indices less than will have scope to be its child node.\n\nNow let\'s think of a recursive solution(top-down), For each number from left to right (n-1, 0) as root, let\'s check how many trees can be made, and let\'s sum it up.\n\nOn recursion, we can check on 0 to i - 1 for finding the left child value and right child value.\n\nIf we find left and right children we can run recursion on both of them as roots, and their results multiplication will give us the answer(multiplication to get different combinations). Sorry, I am not good at explanations.\n\n**Note**: Taking a map to store index after sort so we can easily check if the right child can be found for the respective left child.\n\n**Driver code:**\n```\nint numFactoredBinaryTrees(vector<int>& arr) {\n\tsort(arr.begin(), arr.end());\n\n\tint n = arr.size();\n\tunordered_map<int, int> mp;\n\tfor (int i = 0; i < n; i++) {\n\t\tmp[arr[i]] = i;\n\t}\n\n\tlong ans = 0; \n\tfor (int i = n - 1; i >= 0; i--) {\n\t\tans = (ans + rec(arr, i, mp)) % MOD;\n\t}\n\n\treturn ans;\n}\n```\n\n**Recurssion:**\n```\nlong rec(vector<int>& arr, int i, unordered_map<int, int>& mp) {\n\tlong ans = 1;\n\tfor (int j = 0; j < i; j++) {\n\t\tif (arr[i] % arr[j] == 0 && mp.find(arr[i] / arr[j]) != mp.end()) {\n\t\t\tlong left = rec(arr, j, mp);\n\t\t\tlong right = rec(arr, mp[arr[i] / arr[j]], mp);\n\t\t\tans = (ans + (left * right)) % MOD;\n\t\t}\n\t}\n\treturn ans;\n}\n```\n\nOptimizing this with DP memoization because this has overlaping sub problem. (Take the example input and try to draw the recursive call). DP can be implemented by few modifications.\n\n**Driver Code:**\n```\nvector<int> dp(n, -1);\nfor (int i = n - 1; i >= 0; i--) {\n\t// Last parameter dp array\n\tans = (ans + memo(arr, i, mp, dp)) % MOD;\n}\n```\n\n**Memoization:**\n```\nlong memo(vector<int>& arr, int i, unordered_map<int, int>& mp, vector<int>& dp) {\n\tif (dp[i] != -1) return dp[i]; // Add on\n\tlong ans = 1; \n\tfor (int j = 0; j < i; j++) {\n\t\tif (arr[i] % arr[j] == 0 && mp.find(arr[i] / arr[j]) != mp.end()) {\n\t\t\tlong left = memo(arr, j, mp, dp);\n\t\t\tlong right = memo(arr, mp[arr[i] / arr[j]], mp, dp);\n\t\t\tans = (ans + (left * right)) % MOD;\n\t\t}\n\t}\n\treturn dp[i] = ans; // Add on\n}\n```\n\n\nSo lets optimize memoization to reduce recursive stack space, we can use tabulation(bottom-up).\n\n**Driver Code:**\n```\nvector<int> dp(n, 0);\ntabu(arr, n, mp, dp);\nfor (int i = 0; i < n; i++) {\n\tans = (ans + dp[i]) % MOD;\n}\n\nreturn ans;\n```\n\n\n**Tabulation Code:**\n```\nvoid tabu(vector<int>& arr, int n, unordered_map<int, int>& mp, vector<int>& dp) {\n\tfor (int i = 0; i < n; i++) {\n\t\tint ans = 1;\n\t\tfor (int j = 0; j < i; j++) {\n\t\t\tif (arr[i] % arr[j] == 0 && mp.find(arr[i] / arr[j]) != mp.end()) {\n\t\t\t\tlong left = dp[j];\n\t\t\t\tlong right = dp[mp[arr[i] / arr[j]]];\n\t\t\t\tans = (ans + (left * right)) % MOD;\n\t\t\t}\n\t\t}\n\t\tdp[i] = ans;\n\t}\n}\n```\n\nWe can\'t further space optimaize this because of `dp[mp[arr[i] / arr[j]]]` which can be any previous index.
['Dynamic Programming', 'Recursion', 'Memoization', 'C']