[Coding Made Simple] Count number of binary search tree possible given n keys

Given n which is total number of keys in BST, how many BSTs can be formed with n keys.

Solution 1. Recursion

 1 public class TotalBst {
 2     public int getTotalBst(int n) {
 3         if(n <= 1) {
 4             return 1;
 5         }
 6         int cnt = 0;
 7         for(int rootIdx = 0; rootIdx < n; rootIdx++) {
 8             cnt += getTotalBst(rootIdx) * getTotalBst(n - 1 - rootIdx);
 9         }
10         return cnt;
11     }
12 }

Solution 2. Dynamic Programming

 1 public int getTotalBst(int n) {
 2     int[] T = new int[n + 1];
 3     T[0] = 1;
 4     for(int i = 1; i <= n; i++) {
 5         for(int j = 0; j < i; j++) {
 6             T[i] += T[j] * T[i - 1 - j];
 7         }
 8     }
 9     return T[n];
10 }