#include <vector>
#include <iostream>

using namespace std;

vector<int> cache;

int numTrees(int n) {
    if (n == 0 || n== 1) return 1;
    
    if (cache.size() <= n) cache.resize(n+1);
    
    if (cache[n] > 0) return cache[n];
    
    int num = 0;
    for (int i = 0; i < n; ++i) {
        num += numTrees(i)*numTrees(n-i-1);
    }
    
    cache[n] = num;
    return cache[n];
}

int main (int argc, const char * argv[]) {
    
    for (int i = 1; i <= 15; ++i) {
        cout << i << '\t'<< numTrees(i) << endl;
    }

    return 0;
}

// Output:
// 1   1
// 2   2
// 3   5
// 4   14
// 5   42
// 6   132
// 7   429
// 8   1430
// 9   4862
// 10  16796
// 11  58786
// 12  208012
// 13  742900
// 14  2674440
// 15  9694845