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

Example:

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

---

给定n，问保存1~n的二叉搜索树共有多少种形式。注意要充分利用二叉搜索树的特点，左孩子小于等于根节点，根节点小于等于右孩子。如果trees[0,…,n-1]保存了0,…,n-1个节点的二叉搜索树的个数，现在要求trees[n]。n个节点，除了根节点，剩余n-1个节点，根据选取的根节点的不同，把n-1个节点分在了不同的左右子树中，以该节点为根的有效的二叉搜索树个数等于左右孩子有效的二叉搜索树个数乘积。
以3个点为例，如下图所示，如果选取1作为根节点，则左右孩子的节点数分别为0,2，所以可以有的二叉搜索树形式为trees[0]*trees[2]；如果选取2作为根节点，则左右孩子的节点数分别为1,1，所以可以有的二叉搜索树形式为trees[1]*trees[1]；同理3为trees[2]*trees[0]。

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

所以trees[n]=trees[0]*trees[n-1]+trees[1]*trees[n-2]+…+trees[n-1]*trees[1]。这其实就是卡特兰数：

完整代码如下：

class Solution {
public:
    int numTrees(int n)
    {
        if (n <= 1)
            return 1;
        vector<int> trees(n + 1);
        trees[0] = 1;
        trees[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                trees[i] += trees[j] * trees[i – j – 1];
            }
        }
        return trees[n];
    }
};

本代码提交AC，用时0MS。