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的根节点分别是1,2,..n时对应的BST树的个数。当我们确定了BST的根节点k，那么以k为根节点的BST的个数等于左BST子树的个数乘以右BST子树的个数。还有一点值得注意的是对于给定的节点数BST的个数是一定的，根据这个我们可以做进一步的优化。代码如下：

class Solution {public:    int numTrees(int n) {        if(n == 0 || n == 1) return 1;        int result = 0;                for(int i = 1; i <= n/2; i++)            result += numTrees(i-1)*numTrees(n-i);                return (n%2 == 0)?(2*result):(pow(numTrees(n/2),2) + 2*result);    }};

此外，有这句"当我们确定了BST的根节点k，那么以k为根节点的BST的个数等于左BST子树的个数乘以右BST子树的个数”，我们可以用动态规划的方法解。递推公式可写为：

f(i) = sum(f(k-1)*f(i-k))其中k = 1,2,...i. 时间复杂度为O(n^2)，空间复杂度为O(n)。代码如下：

class Solution {public:    int numTrees(int n) {        vector
     
       f(n+1, 0);                f[0] = 1;        for(int i = 1; i <= n; i++)            for(int k = 1; k <= i; k++)                f[i] += f[k-1] * f[i-k];                return f[n];    }};