[Leetcode] Unique Binary Search Trees

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

Solution:

递归，由于是二叉查找树，先选择任一结点根结点，假设为结点i，则[1，i-1]范围的结点为结点i的左子树结点，[i+1，n]范围的结点为结点i的右子树结点，则以结点i为根结点的BST个数为左，右子树可构成BST个数的乘积，基于这个思路，可以写出以下递归程序。

 1 public class Solution {
 2     public int numTrees(int n) {
 3         if (n < 3)
 4             return n;
 5         return numTrees(1, n);
 6     }
 7     private int numTrees(int start, int end) {
 8         // TODO Auto-generated method stub
 9 
10         if (start >= end)
11             return 1;
12         int result = 0;
13         for (int i = start; i <= end; ++i) {
14             result += numTrees(start, i - 1) * numTrees(i + 1, end);
15         }
16         return result;
17     }
18 }

---------------------------------------------------------------------------------------------------

20150216

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

http://blog.csdn.net/linhuanmars/article/details/24761459