[LeetCode]Unique BST

arr[i] 代表树的大小为 i 时，能组成 unique BST 的个数

• arr[k] = Sum(arr[j - 1] * arr[k - j])  1 <= j <= k

因为左子树的大小可以在 [0, k] 的范围内，右子树也是相应的，时间复杂度 O(n ^ 2)，代码如下：

	public class Solution {
	public int numTrees(int n) {
	if (n < 2)
	return 1;
	int[] arr = new int[n + 1];
	arr[0] = 1;
	arr[1] = 1;
	for (int i = 2; i <= n; i++) {
	int sum = 0;
	for (int j = 0; j < i; j++)
	sum += (arr[j] * arr[i - 1 - j]);
	arr[i] = sum;
	}
	return arr[n];
	}
	}

view raw unique bst.java hosted with ❤ by GitHub