#include <bits/stdc++.h>

using namespace std;
const int N = 20;

// 学习视频
// https://www.bilibili.com/video/BV1nE411A7ST
int g[N];

// f(0)*f(n-1)+f(1)*f(n-2)+....+f(n-1)*f(0)
// 递归
int f(int n) {
    if (n <= 1) return 1;
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += f(i) * f(n - 1 - i);
    return sum;
}

int main() {
    // 1、递推法
    g[0] = g[1] = 1;

    for (int i = 2; i < N; i++)
        for (int j = 0; j < i; j++)
            g[i] += g[j] * g[i - 1 - j]; // 考虑思路：画括号法

    for (int i = 0; i < N; i++)
        cout << g[i] << endl;

    // 2 、递归法
    for (int i = 0; i < N; i++)
        cout << f(i) << endl;
    return 0;
}