两种解题思路

思路1，找递推（递归）关系式：定义：f(x, y)表示待入栈元素 x 个，栈内已有元素 y 个的情况下 可能输出序列的总数目。题目中求解的问题可表示为：f(n, 0)。

每个时刻栈的操作只有两个：入栈、出栈。 把这两种操作所对应的 可能输出序列总数量 加起来即得答案。
入栈：待入栈元素少一个，栈内元素加一个。 对应状态为：f(x-1, y+1)；
出栈：待入栈元素不变，栈内元素少一个。 对应状态为：f(x, y-1)；

则求解 f(x, y) 转化成了求解 f(x-1, y+1)+f(x, y-1)。

找到递推（递归）关系式，可用递推（二维递推），或者递归函数求解，递推注意边界条件的设置，递归注意递归出口的设置，对于本题，递归的方法因为牵涉到某些问题的反复求解，部分样例会超时。

递归实现代码

#include<bits/stdc++.h>
using namespace std;
int n;
//待入栈元素x个，栈内已有y个元素，所对应的输出序列的总数目
int c(int x, int y){
	if(x<0 || y>n) return 0;
	if(x==0) return 1;
	int ans=0;
	//每次可进行的操作：入栈、出栈 
	//入栈-待入栈元素少一个，栈内元素增加一个 c(x-1, y+1);
	//出栈-待入栈元素不变，栈内元素少一个 c(x, y-1);
	if(x>0) ans+=c(x-1, y+1);
	if(y>0) ans+=c(x, y-1);
	return ans;
} 
int main() {
	cin>>n;
	cout<<c(n, 0); 
	return 0;
}

递推实现代码

#include<bits/stdc++.h>
using namespace std;
int n, c[20][20]; //c[i][j] 表示待入栈元素i个，栈内已有元素j个，所对应的输出序列的总数目
void init(){
    for(int j=0; j<=18; j++) c[0][j]=1; //待入栈0，栈内j，只有一种可能的输出序列
    for(int i=1; i<=18; i++){
        c[i][0]=c[i-1][1]; //待入栈i，栈内0，此时只能入栈，不能出栈
        for(int j=1; j<=18; j++){
            c[i][j]=c[i-1][j+1]+c[i][j-1];
        }
    }
}
int main() {
    init();
	cin>>n;
	cout<<c[n][0]; 
	return 0;
}

思路2：卡特兰数-组合数学中一种重要的计数数列，用于描述“合法匹配”、“不越界”、“分治拆分”类问题的计数规律。本题涉及问题即为卡特兰数的一个典型应用场景。
卡特兰数：1、1、2、5、14、42、132...

原理：
$f(n+1)=\sum_{i=0}^{n} f(i)*f(n-i)$ (n>=0)
规模为 n+1 的问题，可以拆分成规模为 i 的问题和规模为 n-i 的两个子问题，累加所有情况。

卡特兰数的通项公式：$f(n)=\dfrac{(2n)!}{(n+1)!\cdot n!}$

本题n的值最大为18，如果直接使用卡特兰数的通项公式，会面临超出64位有符号整数存储范围的问题。因此要利用原理进行逐个推导。
$f(n)=\sum_{i=0}^{n-1} f(i)*f(n-1-i)$ (n>=0)

卡特兰数

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

感兴趣的同学可以再去查找一下卡特兰数的其他应用场景。