96. Unique Binary Search Trees

1. 正常的解法：动规

从理解上说，

n = 1，有1种可能

n = 2， 有2种可能，a.左子树0节点，右子树1个 b.左子树1个节点，右子树零个

n = 3，有三个节点，这个数的组成可能是，选任意一个作为根节点，然后a.左子树有0个节点，右子树2个 b.左子树一个节点，右子树一个节点 c.左子树2个节点，右子树0个。所以结果是res[0]*res[2] + res[1] * res[1] + res[2] * res[0] = 5

n = 4, 同理，res[4] = res[0] * res[3] + res[1] * res[2] + res[2] * res[1] + res[3] * res[0] = 14

....

所以

 1     public int numTrees(int n) {
 2         if(n <= 0) {
 3             return 0;
 4         } 
 5         int[] res = new int[n+1];
 6         res[0] = 1;
 7         res[1] = 1;
 8         for(int i = 2; i <= n; i++) {
 9             for(int j = 0; j < i; j++) {
10                 res[i] += res[j] * res[i-1-j];
11             }
12         }
13         return res[n];
14     }

2. 数学解法：卡特兰数

其实我觉得这个没必要这么做……毕竟不是数学专业，不是刷题哪知道这个公式= =

公式是：

就不写了

96. Unique Binary Search Trees

原文：http://www.cnblogs.com/warmland/p/5457086.html