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

正统的做法就是遍历所有情况，累计结果（解法１）

优雅的做法就是识别出结果是卡特兰数，该题符合卡特兰数的递推公式：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)。

因此可以直接使用卡特兰数的计算公式：h(n)=C(2n,n)/(n+1) (n=0,1,2,...)，得到解法２

解法１

public class UniqueBinarySearchTrees {
	public int numTrees(int n) {
		if (n <= 1) {
			return 1;
		}

		int[] records = new int[n + 1];
		records[0] = records[1] = 1;
		for (int i = 2; i <= n; ++i) {
			for (int k = 0; k < i; ++k) {
				records[i] += records[k] * records[i - 1 - k];
			}
		}
		return records[n];
	}
}

public class UniqueBinarySearchTrees {
	public int numTrees(int n) {
		if (n <= 1) {
			return n;
		}
		int catalanNum = 1;
		for (int i = 2; i <= n; ++i) {
			catalanNum = catalanNum * 2 * (2 * i - 1) / (i + 1);
		}
		return catalanNum;
	}
}

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

LeetCode |　Unique Binary Search Trees

原文：http://blog.csdn.net/perfect8886/article/details/21110863