Сложность: medium
Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n.
Пример:
Input: n = 3
Output: 5
👨💻 Алгоритм:
1⃣Задача состоит в том, чтобы рассчитать количество уникальных BST (бинарных деревьев поиска). Для этого мы можем определить две функции:
G(n): количество уникальных BST для последовательности длины n.
F(i, n): количество уникальных BST, где число i является корнем BST (1 ≤ i ≤ n).
Как видно, G(n) - это именно та функция, которая нам нужна для решения задачи.
2⃣Позднее мы увидим, что G(n) можно вывести из F(i, n), которая, в свою очередь, рекурсивно относится к G(n).
Следуя идее из раздела "Интуиция", мы видим, что общее количество уникальных BST G(n) равно сумме BST F(i, n) с перечислением каждого числа i (1 ≤ i ≤ n) в качестве корня. Таким образом,
G(n) = ∑ F(i, n) для i от 1 до n.
В частности, для базовых случаев есть только одна комбинация для построения BST из последовательности длиной 1 (только корень) или ничего (пустое дерево). То есть G(0) = 1, G(1) = 1.
3⃣Дана последовательность от 1 до n, мы выбираем число i из последовательности в качестве корня, тогда количество уникальных BST с указанным корнем, определенным как F(i, n), является декартовым произведением количества BST для его левого и правого поддеревьев, как показано ниже:
Например, F(3,7) - количество уникальных деревьев BST с числом 3 в качестве корня. Для построения уникального BST из всей последовательности [1, 2, 3, 4, 5, 6, 7] с 3 в качестве корня, мы должны построить поддерево из его левой подпоследовательности [1, 2] и другое поддерево из правой подпоследовательности [4, 5, 6, 7], а затем соединить их вместе (то есть декартово произведение). Теперь хитрость заключается в том, что мы можем рассматривать количество уникальных BST из последовательности [1,2] как G(2), и количество уникальных BST из последовательности [4, 5, 6, 7] как G(4). Для G(n) не имеет значения содержание последовательности, а только длина последовательности. Следовательно, F(3,7) = G(2)⋅G(4). Обобщая пример, мы можем вывести следующую формулу:
F(i, n) = G(i−1)⋅G(n−i)
Объединяя формулы (1), (2), мы получаем рекурсивную формулу для G(n), то есть
G(n) = ∑ G(i−1)⋅G(n−i) для i от 1 до n.
Чтобы вычислить результат функции, мы начинаем с меньшего числа, так как значение G(n) зависит от значений G(0)...G(n−1).
😎 Решение:
class Solution {
func numTrees(_ n: Int) -> Int {
var G = Array(repeating: 0, count: n + 1)
G[0] = 1
G[1] = 1
for i in 2...n {
for j in 1...i {
G[i] += G[j - 1] * G[i - j]
}
}
return G[n]
}
}Ставь 👍 и забирай 📚 Базу знаний