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

基本思路：

题目的意思就是给一个整数n，找出含有n个节点的BST。动态规划，每次以一个数作为跟，然后计算左子树的BST数乘以右子树的BST数。

	public int numTrees(int n)
	{
		int[] numtree = new int[n+1];
		for(int i = 0;i<=n;i++)
		{
			//0个节点和1个节点的情况都返回1
			if(i==1||i==0)
				numtree[i] = 1;
			else
			{
				//计算当根节点的左边有j个节点，右边有i-j-1个节点时
				//此时数的数目为 左边的数目乘以右边的数目
				int temp = 0;
				for(int j = 0;j<i;j++)
				{
					temp+=(numtree[j]*numtree[i-j-1]);
				}
				numtree[i] = temp;
			}
		}
		return numtree[n];
	}

Unique Binary Search Trees,布布扣,bubuko.com

Unique Binary Search Trees

原文：http://blog.csdn.net/cow__sky/article/details/22086563