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;
	}
}