HW3_brackets2

#include <cstdio>
#include <cstdlib>

int main()
{
    int n = 0;
    scanf("%d", &n);
    int** arr = (int**)malloc((n+1)*sizeof(int**));
    for (int i = 0; i <= n; i++)
    {
        arr[i] = (int*)malloc((n - i + 1)*sizeof(int));
        if (i == 0)
        {
            for (int j = 0; j <= n; j++)
                arr[i][j] = 1;
        }
        else
        {
            arr[i][0] = arr[i - 1][1];
            for (int j = 1; j <= (n - i); j++)
                arr[i][j] = arr[i - 1][j + 1] + arr[i][j - 1];
        }
    }
    printf("%d\n", arr[n][0]);
    return 0;
}