DP #40. Count number of Binary Search Trees - mbhushan/dynpro GitHub Wiki
(40). Count number of binary search trees.
Given n which is total number of keys in BST, how many BSTs
can be formed with n keys
public int countBSTs(int n) {
if (n == 0 || n == 1) {
return 1;
}
int [] T = new int[n+1];
T[0] = 1;
T[1] = 1;
for (int i=2; i<=n; i++) {
for (int j=0; j<i; j++) {
T[i] += (T[j] * T[i-j-1]);
}
}
return T[n];
}