Задача: 96. Unique Binary Search Trees
Сложность: medium

Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n.

Пример:

Input: n = 3
Output: 5

👨‍💻 Алгоритм:

1⃣Вводим G(n) — количество уникальных BST, которые можно построить из n узлов.

2⃣Для каждого i от 1 до n, количество деревьев с i в качестве корня равно G(i−1) * G(n−i), где i−1 — количество узлов в левом поддереве, а n−i — в правом.

3⃣Для подсчета G(n) используем динамическое программирование с базовыми случаями:
G(0) = 1 (пустое дерево)
G(1) = 1 (один узел)

😎 Решение:

class Solution {
    function numTrees($n) {
        $G = array_fill(0, $n + 1, 0);
        $G[0] = $G[1] = 1;

        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                $G[$i] += $G[$j - 1] * $G[$i - $j];
            }
        }

        return $G[$n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний