Leetcode 96. 不同的二叉搜索树

感谢Leetcode官方送给的圣诞帽，Merry Christmas ！唔哈~~~~

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:　

　　　输入: 3
　　　输出: 5
　　　解释:
　　　　给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

分析：

　　此题可以采用动态规划来计算种类数

　　令f(n)表示，n个节点可以构成的二叉搜索树的种类数；

　　当n=1时，只有一种结构，f(n)=1；

　　当n=2时，两个节点分别作为根节点，剩下的一个节点数目和，f(1)+f(1)

　　当n=3时，第一个节点作为根节点，剩下两个节点能够组成，f(2)

　　　　　　　第二个节点作为根结点时，前一个和后一个的和，f(1)*f(1)

　　　　　　　　第三个节点作为根节点是，前两个节点构成，f(2)

　　　　　　因此，当f(3)=f(2)+f(1)*f(1)+f(2)=5

　　当n=4时，f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3)=14

故，我们令f(0)=1，以便于计算

递推式如下

　　f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-2)*f(1)+f(n-1)

代码如下：

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         if(n<=2)
 5             return n;
 6         if(n==3)
 7             return 5;
 8         vector<int> a;
 9         a.resize(n+1,0);
10         a[0]=1;
11         a[1]=1;
12         a[2]=2;
13         a[3]=5;
14         for(int i=4;i<n+1;i++)
15         {
16             for(int j=0;j<i;j++)
17             {
18                 a[i]+=(a[j]*a[i-j-1]);
19             }
20         }
21         return a[n];
22     }
23 };

另一种数学解法，直接返回 C(2n,n) / (n+1)