LeetCode 96. Unique Binary Search Trees

题意：给定一个数n，求出1~n，所有二叉树的个数；

在LeetCode 95中，要你求出所有二叉树，并返回结点，题解见：https://www.cnblogs.com/yy-1046741080/p/11594454.html。

原来我就想用直接递归，来求出结点个数的，结果发现TE；在近期了解了DP后，修改了一下源代码，就顺利过了，但是空间效率并不是很理想，因为DP记录了很多数据，可能也是我DP用的不太好导致的。

另外，关于二维数组的动态内存申请还是值得记忆一下的；（虽然可以使用vector来定义指定长度）

要点：

递归函数：计算 [left,right) 序列形成的二叉树个数；在该函数，令每一个点都可以作为顶点，然后每一次个数等于左子树个数*右子树个数；然后累加就得到结果；在递归边界时，为1 ；
使用array[left][right)来记录[left,right）序列生成的二叉树个数；默认为-1；如果不为-1，说明已经计算过了，直接套用就行了。（我认为的DP的关键就是：减少重复计算，以空间换取时间）

 1 class Solution {
 2 public:
 3     // [left,right)
 4     int CalNum(int left,int right,int** array){
 5         if(left>=right){
 6             array[left][right]=1;
 7             return 1;
 8         }
 9         else{
10             int sum=0;
11             for(int i=left;i<right;i++){
12                 if(array[left][i]==-1){
13                     array[left][i]=CalNum(left,i,array);
14                 }
15                 if(array[i+1][right]==-1){
16                     array[i+1][right]=CalNum(i+1,right,array);
17                 }
18                 sum+=array[i+1][right]*array[left][i];
19             }
20             return sum;
21         }
22     }
23     
24     int numTrees(int n) {
25         // DP array  
26         int** array;
27         array=new int*[n+2];
28         for(int i=1;i<=n+1;i++){
29             array[i]=new int[n+2];
30             for(int j=1;j<=n+1;j++){
31                 array[i][j]=-1;
32             }
33         }
34         
35         return CalNum(1,n+1,array);
36     }
37 };

实际上，可以对上述的DP进行简化，在上述代码中，我采用的array[i][j]表示的是从[i,j)的数构成的最小生成树个数；

重新思考一下，既然是考虑个数，123和456形成的最小生成树个数又有何区别？

因此，将array[i][j]变为array[i]，作为i个结点时最小生成树的个数。这样就大大地简化了计算量。

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         int *cnt = (int*)malloc((n+1)*sizeof(int));
 5         memset(cnt, 0, (n+1)*sizeof(int));
 6         cnt[0] = 1;
 7         cnt[1] = 1;
 8     
 9         for (int i=2; i<=n; i++){
10             for(int j=0; j<i; j++){
11                 cnt[i] += cnt[j]*cnt[i-j-1];  // 左子树个数乘以右子树个数！
12             }
13         }
14         int sum = cnt[n];
15         free(cnt);
16         return sum;
17     }
18 };

Catalan number：

满足递推公式：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) (h(0)=1,h(1)=1)
直接计算公式：h(n)=C(2n,n)/(n+1) = 2n! / n! (n+1)! (n=0,1,2,...)
递推公式是其本质规律，因此，如果在递归中发现该公式，那么就是Catalan number；如果知道其是Catalan number，那么可以采用直接计算公式；
一些Catalan number的实例：
1. 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? （对于第i个元素进栈，设f(i)为1~i元素出栈序列个数，f(i) = f (i-1) * f (n-i+1) ；因此符合Catalan）
2. 对于1~n构成的二叉搜索树个数，同样满足Catalan，递推公式见第二段代码。

对于Catalan数，只需要知道其本质就行了，关键还是寻找到递推公式。

LeetCode 96. Unique Binary Search Trees

相关推荐