https://leetcode.com/problems/binary-trees-with-factors/description/
https://www.jianshu.com/p/d861251c2ec3
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-823-binary-trees-with-factors/
https://leetcode.com/problems/binary-trees-with-factors/discuss/126277/Concise-Java-solution-using-HashMap-with-detailed-explanation.-Easily-understand!!!
https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C++JavaPython-DP-solution
Given an array of unique integers, each integer is strictly greater than 1.
We make a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node's value should be equal to the product of the values of it's children.
How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.
Example 1:
Input:A = [2, 4]Output: 3 Explanation: We can make these trees:[2], [4], [4, 2, 2]
Example 2:
Input:A = [2, 4, 5, 10]Output:7Explanation: We can make these trees:[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
Note:
1 <= A.length <= 1000.2 <= A[i] <= 10 ^ 9.
https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C%2B%2BJavaPython-DP-solution
with
Sort the list
DP equation:
A at first.DP equation:
dp[i] = sum(dp[j] * dp[i / j])res = sum(dp[i])with
i, j, i / j in the list L public int numFactoredBinarydps(int[] A) {
long res = 0L, mod = (long) Math.pow(10, 9) + 7;
Arrays.sort(A);
HashMap<Integer, Long> dp = new HashMap<>();
for (int i = 0; i < A.length; ++i) {
dp.put(A[i], 1L);
for (int j = 0; j < i; ++j)
if (A[i] % A[j] == 0 && dp.containsKey(A[i] / A[j]))
dp.put(A[i], (dp.get(A[i]) + dp.get(A[j]) * dp.get(A[i] / A[j])) % mod);
}
for (long v : dp.values()) res = (res + v) % mod;
return (int) res;
}
The largest value
v used must be the root node in the tree. Say dp(v) is the number of ways to make a tree with root node v.
If the root node of the tree (with value
v) has children with values x and y (and x * y == v), then there are dp(x) * dp(y) ways to make this tree.
In total, there are ways to make a tree with root node
v.
Algorithm
Actually, let
dp[i] be the number of ways to have a root node with value A[i].
Since in the above example we always have
x < v and y < v, we can calculate the values of dp[i] in increasing order using dynamic programming.
For some root value
A[i], let's try to find candidates for the children with values A[j] and A[i] / A[j] (so that evidently A[j] * (A[i] / A[j]) = A[i]). To do this quickly, we will need index which looks up this value: if A[k] = A[i] / A[j], then index[A[i] / A[j]] = k`.
After, we'll add all possible
dp[j] * dp[k] (with j < i, k < i) to our answer dp[i]. In our Java implementation, we carefully used long so avoid overflow issues.public int numFactoredBinaryTrees(int[] A) { int MOD = 1_000_000_007; int N = A.length; Arrays.sort(A); long[] dp = new long[N]; Arrays.fill(dp, 1); Map<Integer, Integer> index = new HashMap();// for (int i = 0; i < N; ++i) index.put(A[i], i); for (int i = 0; i < N; ++i) for (int j = 0; j < i; ++j) { if (A[i] % A[j] == 0) { // A[j] is left child int right = A[i] / A[j]; if (index.containsKey(right)) { dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD; } } } long ans = 0; for (long x: dp) ans += x; return (int) (ans % MOD); }
一个典型的dp问题, 令dp[i]为根节点是A[i]的树的个数。可以先把数组sort一下.
那可想而知: 当 tmp = A[i] * A[j]
dp[tmp] = dp[i] * dp[j] * 2 (i != j)
dp[tmp] = dp[i] * dp[j] (i == j)
我的代码里面用HashMap代替了dp数组
Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].
dp[i] = sum(dp[j] * dp[i/j]), 0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.
ans = sum(dp[i]), for all possible i.
/**sort the array
* and use HashMap to record each Integer, and the number of trees with that Integer as root
* (1) each integer A[i] will always have one tree with only itself
* (2) if A[i] has divisor (a) in the map, and if A[i]/a also in the map
* then a can be the root of its left subtree, and A[i]/a can be the root of its right subtree;
* the number of such tree is map.get(a) * map.get(A[i]/a)
* (3) sum over the map
*/
public int numFactoredBinarydps(int[] A) {
long res = 0L, mod = (long) Math.pow(10, 9) + 7;
Arrays.sort(A);
HashMap<Integer, Long> dp = new HashMap<>();
for (int i = 0; i < A.length; ++i) {
dp.put(A[i], 1L);
for (int j = 0; j < i; ++j)
if (A[i] % A[j] == 0 && dp.containsKey(A[i] / A[j]))
dp.put(A[i], (dp.get(A[i]) + dp.get(A[j]) * dp.get(A[i] / A[j])) % mod);
}
for (long v : dp.values()) res = (res + v) % mod;
return (int) res;
}