题解：P1044 [NOIP 2003 普及组] 栈

及问你有 $n$ 个数 $1$ 到 $n$，让你求出栈序列的情况总数。

这个题目是经典的数学题，在这里我们硬求肯定是没有办法的，那么我们不妨以递推的视角看一下。 我们可以设一个数组 $f$ 为在当 $n$ 为一到十八时，可能的序列总数。 那么此时我们的 $f_0$ 和 $f_1$ 只有一种情况，而 $f_2$ 有两种。 那么我们可以先构造一个栈的结构，我们得到了一个输入序列，接下来就要处理了，下一步求递推公式便是本题的精髓，我们的序列是不是从 $1$ 到 $n$ 的，我们的 $i$ 从一开始循环。那么，我们随机挑一个点 $k$，以 $k$ 为中心点我们的序列被劈成了两半，这两段的情况数为 $f_{k-1}$ 和 $f_{i-k}$ 这两个，那么根据乘法原理，总可能性为 $f_{k-1}$ $\times$ $f_{i-k}$ 。最终公式为 $f_n$ $=$ $f_0$ $\times$ $f_{n-1}$ $+$ $f_1$ $\times$ $f_{n-2}$ $\cdots$ $+$ $f_{n-1}$ $\times$ $f_0$。 那么，我们进行枚举，将 $1$ 到 $n$ 每一个数做这样的处理，将得出的数相乘，就是本题的答案。

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