# Leetcode 96 - Unique Binary Search Tree

`Note:`

- May 2022 update
- Forget about DP coz it’s from some math formula, it’s more instinctive to use
`DFS`

. - Remember to use a memo to remember result we’ve got. The key should be
`left.right`

.

- Forget about DP coz it’s from some math formula, it’s more instinctive to use

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

**Example:**

1 | Input: n = 3 |

1 | /** |

`DP[i]`

represents the number of unique BST trees.- The DP formula is
`DP[i] += DP[j] + DP[i-j-1]`

.- Explaination:
`DP[3] = DP[0]*DP[2] + DP[1]*DP[1] + DP[2]*DP[0]`

. - For n=3, when 1 is the root, the number of trees with 1 as the root is
`DP[0]*DP[2]`

. When 2 is the root, the number of trees with 2 as the root is`DP[1]*DP[1]`

. When 3 is the root, the number of trees with 3 as the root is`DP[2]*DP[0]`

.

- Explaination:

1 | /** |