Given n, how many structurally unique BST‘s (binary search trees) that store values 1...n?

For example,
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

BST树的定义：根节点左边所有节点的值小于根节点值，右边所有节点的值大于根节点的值，然后其左右子树又是BST

思路：例如序列：1,2,3,4,5

第一个数字的左边有0个数字，右边4个数字  dp[0]*dp[4]

第二个数字的左边有1个数字，右边3个数字  dp[1]*dp[3]

第三个数字的左边有2个数字，右边2个数字  dp[2]*dp[2]

第四个数字的左边有3个数字，右边1个数字  dp[3]*dp[1]

第五个数字的左边有4个数字，右边0个数字  dp[4]*dp[0]

所以我们要求的dp[5]就等于上面加起来的和，这里我们得假设dp[0]=1;

 其实就是每个数字来当根节点，具体如下图所示

代码：

class Solution{public:    int numTrees(int n) {        if(n<=1) return n;        vector<int> dp(n+1,0);                dp[0]=1;        for(int i=1;i<=n;++i){            int temp=0;            for (int j=1;j<=i;++j)            {                temp+=dp[j-1]*dp[i-j];            }            dp[i]=temp;        }        return dp[n];    }};

Unique Binary Search Trees（dp）