题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。
栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，1,2,⋯ ,n1,2,\cdots ,n（图示为 1 到 3 的情况），栈 A 的深度大于 nn。

现在可以进行两种操作：

  • 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）；
  • 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）。

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

你的程序将对给定的 nn，计算并输出由操作数序列 1,2,⋯ ,n1,2,\cdots,n 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 nn（1≤n≤181 \leq n \leq 18）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例

输入 #1

1
3

输出 #1

1
5

说明/提示

【题目来源】
NOIP 2003 普及组第三题

思路

暴力搜索

考虑每次操作从栈中弹出还是向栈中增加新的数。

x,string cur,string res)```表示已经考虑完第 $x$ 个数，栈中的序列为 $cur$，弹出的序列为 $res$；递归入口为```DFS(0,"","")```，当 $res$ 的长度为 $n$ 时，存入哈希表，最终的答案为哈希表的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
```cpp
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1044
Date: 2021 Mar. 16th
Description: DFS
*******************************************************************/
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
unordered_set<string>ans;
int n;
void DFS(int x,string cur,string res){
	if(res.size()==n){
		ans.insert(res);
		return;
	}
	if(cur.length()){
		//栈中弹出一个
		string nxt=cur;
		nxt.pop_back();
		DFS(x,nxt,res+cur.back());
	}
	//进栈
	if(x==n){
		return;
	}
	string nxt=cur+(char)(x+'1');
	DFS(x+1,nxt,res);
}
int main() {
	cin>>n;
	DFS(0,"","");
	cout<<ans.size()<<endl;
	return 0;
}

上面的代码妥妥超时了，第一反应是：string类型的拷贝太耗时间，且每次得到的 resres 都不同，没必要去重。将哈希表去掉后可以看到，我们只在意 resres 的长度，并不在意 curcur 和 resres 的内容，因此直接用int类型即可。

x,int cur,int res)```表示当前已经考虑完第 $x$ 个数，栈中有 $cur$ 个数，已经输出 $res$ 个数的状态；入口为```DFS(0,0,0)```，当 $res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
显然是超时了，$n=18$ 时有 $477638700$ 种情况。  

```cpp
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1044
Date: 2021 Mar. 16th
Description: DFS
*******************************************************************/
#include<iostream>
using namespace std;
int n;
int ans;
void DFS(int x, int cur, int res) {
	if (res == n) {
		++ans;
		return;
	}
	if (cur) {
		//栈中弹出一个
		DFS(x, cur - 1, res + 1);
	}
	//进栈
	if (x == n) {
		return;
	}
	DFS(x + 1, cur + 1, res);
}
int main() {
	cin >> n;
	DFS(0, 0, 0);
	cout << ans << endl;
	return 0;
}

记忆化搜索

在上述搜索的参数中，显然有 res+cur=xres+cur=x，我们记录了多余的状态。采用记忆化搜索的方式，当 cur+res=ncur+res=n 时，返回临界值 11。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1044
Date: 2021 Mar. 16th
Description: DFS
*******************************************************************/
#include<iostream>
using namespace std;
int n;
int f[22][21];
int DFS(int cur, int res) {
	if (f[cur][res]) {
		return f[cur][res];
	}
	if (cur + res == n) {
		return f[cur][res] = 1;
	}
	int ans = 0;
	if (cur) {
		ans += DFS(cur - 1, res + 1);
	}
	ans += DFS(cur + 1, res);
	return f[cur][res] = ans;
}
int main() {
	cin >> n;
	cout << DFS(0, 0) << endl;
	return 0;
}

卡特兰数

令 fnf_n 表示 nn 个数出栈入栈的方法数，则对于 fnf_n，可以用第一个入栈数字出栈的时机作为标准。若首个入栈数字 xx 在 nn 个数字中第 kk 个出栈，那么产生的方案数为 fk−1×fn−kf_{k-1}\times f_{n-k}：fk−1f_{k-1} 为在 xx 之前出栈之前那 k−1k-1 个数的方案，fn−kf_{n-k} 为在 xx 出栈之后那 n−kn-k 个数的方案。
枚举 kk，有 fn=∑k=1nfk−1×fn−kf_n=\sum\limits_{k=1}^n f_{k-1}\times f_{n-k}，这就是卡特兰数的一个递推式。
用 HnH_n 表示卡特兰数的第 nn 项，有 Hn=4n−2n+1Hn−1H_n=\frac{4n-2}{n+1}H_{n-1}，且 H0=1H_0=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1044
Date: 2021 Mar. 16th
Description: Combinatorics
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
ll f[19];//计算过程中会爆int
int main() {
	f[0] = 1;
	for (int i = 1;i <= 18;i++) {
		f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
	}
	int n;
	cin >> n;
	cout << f[n] << endl;
	return 0;
}