#include<bits/stdc++.h>
using namespace std;
int dp[25][25] , n;
int main(){
    cin >> n;
    for(int i = 0;i <= n;i++)dp[0][i] = 1;//初始化
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= n;j++){
            if(j)dp[i][j] = dp[i][j - 1] + dp[i - 1][j + 1];//栈中有元素
            else dp[i][j] = dp[i - 1][j + 1];//栈中无元素
        }
    }
    cout << dp[n][0];
    return 0;
}

先把表打出来：

#include <bits/stdc++.h>
using namespace std;

int n,cnt;

void dfs(int step,int x)
{
	if(step > n)
	{
		cnt++;
		return;
	}
	if(x) dfs(step,x - 1);
	dfs(step + 1,x + 1);
	return;
}

signed main()
{
	for(n = 1;n <= 18;n++)
	{
		cnt = 0;
		dfs(1,0);
		printf("%d,",cnt);
	}
	return 0;
}

得出答案序列：

0,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700

然后输出。

#include <bits/stdc++.h>
using namespace std;

int n;
int ans[19] = {0,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670
,129644790,477638700};

signed main()
{
	scanf("%d",&n);
	printf("%d",ans[n]);
	return 0;
}

搞笑的吧？

#include <bits/stdc++.h>
using namespace std;
 
long long n, a[20];
 
int main ()
{
	cin >> n;
	a[0] = 1, a[1] = 1;
	for (int i = 2; i <= n; ++i)
		for (int j = 0; j <= i - 1; ++j)
			a[i] += a[j] * a[i-1-j];
	cout << a[n];
}

要题解