Сложность: medium
Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.
Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов.
Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7.
Пример:
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
👨💻 Алгоритм:
1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.
2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.
3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.
😎 Решение:
class Solution {
public int numFactoredBinaryTrees(int[] A) {
int MOD = 1_000_000_007;
Arrays.sort(A);
long[] dp = new long[A.length];
Arrays.fill(dp, 1);
Map<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < A.length; i++) {
index.put(A[i], i);
}
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (A[i] % A[j] == 0) {
int right = A[i] / A[j];
if (index.containsKey(right)) {
dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
}
}
}
}
long result = 0;
for (long x : dp) {
result = (result + x) % MOD;
}
return (int) result;
}Ставь 👍 и забирай 📚 Базу знаний