Подсчитайте общее количество уникальных двоичных деревьев поиска — n-ное каталонское число (динам...

Описание: Бесплатный 5-дневный мини-курс: https://backtobackswe.com
Попробуйте нашу полную платформу: https://backtobackswe.com/pricing
📹 Интуитивно понятные видеообъяснения
🏃 Запускайте код по мере обучения
💾 Сохраняйте прогресс
❓Новые, ранее не рассматривавшиеся вопросы
🔎 Получите все решения

Вопрос: При заданном n, сколько структурно уникальных BST (бинарных деревьев поиска), хранящих значения 1 ... n?

Каталонские числа: https://en.wikipedia.org/wiki/Catalan...

Определите G(n): количество уникальных BST для последовательности длины n.

G(0) = 1
G(1) = 1

Для каждого элемента мы можем разместить его и выполнить рекурсию слева направо, не включая число, выбранное нами в качестве корня поддерева.

Определим F(i,n): количество уникальных BST-деревьев, где число i служит корнем BST (1 меньше или равно i, которое меньше или равно n).

G(n) = сумма F(i, n) от 1 до n.

Когда мы выбираем элемент для корневого поддерева из возможных элементов, мы разделяем возможные элементы исходного перечисления на левую и правую части.

Пример:

n ​​= 5, то есть [1, 2, 3, 4, 5]

При вычислении F(3, 5) мы получим
левое поддерево с [1, 2], то есть G(2);
правое поддерево с [4, 5], то есть G(2);

G(n) вычисляет количество уникальных деревьев, которые мы можем построить из n возможных значений, независимо от того, каковы эти значения.

Реализация

Заметим, что F(i, n) = G(i - 1) * G(n - i)

Чтобы получить F(i, n), мы рассматриваем все комбинации вариантов левого дерева со всеми вариантами правого дерева.

Это исчерпывающее сопоставление двух наборов элементов называется декартовым произведением.

Теперь у нас есть новый способ выразить F(i, n)

F(i, n) = G(i - 1) * G(n - i)

G(n) = суммирование от 1 до n значений G(i - 1) * G(n - i)

Теперь это можно решить с помощью DP, используя нисходящую рекурсию или восходящий алгоритм.

Для каждого G(n) вплоть до запрошенного n мы решим уравнение суммирования G(n).

В конце мы возвращаем запрошенное значение G(n), для которого в итоге получим ответ.

++++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Тушар Рой:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Джарвис Джонсон:    / vsympathyv  

Успех в технологиях:    / @successintech