87: Unique binary search trees

Given an integer n, return how many unique binary search trees can be built on values from 1 to n

 

Example

Input:  3

Output: 5

Explanation: can be build 5 unique binary search trees

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