Contents

# Problem

Given n, how many structurally unique (BST) that store values 1 … n?

## example 1

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 ``````

# Solution

## Dynamic programming

Main idea - dynamic programming :

We know that unique bst for `n=1` is `1`, for `n=0` is `1`, for `n=2` is 2. Also, we know than for `n=3 : {1,2,3}` we can check tries with:

• root 1 – its mean that we should check tries right with nodes `{2,3}`
• root 2 – its mean that we should check tries left with nodes `{2}` and right with nodes `{3}`
• root 3 – its mean that we should check tries left with nodes `{1,2}`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````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