题目描述：给定一个值n，能构建出多少不同的值包含1...n的二叉搜索树（BST）？
例如：给定 n = 3, 有五种不同的二叉搜索树（BST）
示例1：
        输入：3
        返回值：5
思路：对于值为n（包含1...n）的二叉搜索树而言，由于二叉搜索树具有下列性质：
                  二叉搜索树左节点的值小于根节点，根节点的值小于右节点。所以一棵二叉搜索树可以这样唯一确定，先确定根节点，然后划分为左右子树两个集合，这样二叉搜索树的数目为左子树个数 乘以 右子树的个数.
                 首先，易知 r(0) = 1 ；r(1) = 1 ；因此，要知道 r(n),可从根节点root出发，对于值为n的二叉搜索树而言，根节点可能为1、2、3、4...n中的任意一个，则分为如下n种情况：
                 如果根节点为1，则左子树中的节点集合为 {NULL} ，右子树中的节点集合为{2,3,...,n} 共 n-1 个节点，共有 r(0)Xr(n-1) 种二叉搜索树。
                 如果根节点为2，则左子树中的节点集合为 {NULL,1} , 右子树中的节点集合为{3,...,n} 共 n-2 个节点，共有 r(1)Xr(n-2) 种二叉搜索树。
                 如果根节点为 i ,则左子树中的节点集合为 {NULL,1,2,...,i-1} ，右子树中的节点集合为{i+1,i+2,...,n} 共 n-i 个节点，共有 r(i-1)Xr(n-i) 种二叉搜索树.
                 如果根节点为n,则左子树中的节点集合为 {NULL,1,2,...,n-1} ，右子树中的节点集合为{} 共 0 个节点，共有 r(n-1)Xr(0) 种二叉搜索树.
        最终对应递推关系公式为 r(n) += r(i-1)*r(n-i), 其中i=1,2,...n.具体代码按如下：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int numTrees(int n) {
        // write code here
        //思路就是找规律，每个都可以作为根节点，然后分为两部分，一部分为左子树，一部分为右子树，左子树小于根节点，右子树大于根节点
        //定义全为0且长度为j+1的一维数组,找规律发现递推公式
        //r(0) = 1
        //r(1) = 1
        //r(n) += r(i-1)*r(n-i), 其中i=1,2,...n
        vector<int> r(n+1,0);
        r[0] = r[1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
                r[i]+=r[j-1]*r[i-j];
        }
        return r[n];
    }
};