Задача

Дано n, сколько существует структурно уникальных (BST), которые хранят значения 1 … n?

Пример 1

Вход: 3
Выход: 5
Объяснение:
Дано n = 3, существует всего 5 уникальных BST:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Решение

Динамическое программирование

Основная идея - динамическое программирование:

Мы знаем, что уникальных BST для n=1 будет 1, для n=0 будет 1, для n=2 будет 2. Также мы знаем, что для n=3 : {1,2,3} мы можем проверить деревья с:

• корнем 1 – это означает, что мы должны проверить деревья справа с узлами {2,3}
• корнем 2 – это означает, что мы должны проверить деревья слева с узлами {2} и справа с узлами {3}
• корнем 3 – это означает, что мы должны проверить деревья слева с узлами {1,2}

func numTrees(n int) int {
    a:= make(map[int]int, 0)
    a[0] = 1
    a[1] = 1
    a[2] = 2
    return helper(n , a)
}

func helper(n int, a map[int]int) int {
    if _, ok := a[n]; ok {
        return a[n]
    }
    res := 0
    for idx := 0; idx<n; idx++ {
        res += (helper(idx, a)*helper(n-idx-1, a))
    }

    a[n] = res

    return a[n]
}