#include <iostream>
#include <string.h>
using namespace std;
int numTrees(int n) {
    //分别以1.i.n为根节点建立二叉树
    //i为根节点，左边 1 ~ i-1, i-1个（满足左边都小于i），
    // 右边 i+1 ~ n，n-i个（满足右边都大于i）
    //dp[n]：n个节点不同二叉树个数为 dp[n]
    //dp[n] = f(1) + f(2) + ... + f(n)
    //f(i)：以i为根节点(1 <= i <= n)的二叉树个数为f(i)
    //f(i) = dp[i-1] * dp[n-i]
    int dp[1+n];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    

    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            //累加f(1)到f(i)
            dp[i] += dp[j-1] * dp[i-j];
        }
    }
    return dp[n];
}

int main(){
    cout << numTrees(6) << endl;
    return 0;
}