1/500
卡特兰数简单来说就是对于一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?下面给出一道较小数据例题并对其分析.
题目

解法一: 递归

递归的思路考虑的是当前状态可以变为哪种状态,并找到递归终点再次进行回溯,下面我们分析数字的三种状态

1. 在队列中
2. 在栈中
3. 出栈

对于状态1有一种操作入栈变为状态2,对于状态2可以选择出栈变为状态3,三种状态有且存在一种变化1->2->3

考虑到数据范围采用普通递归可能会超时,这里使用记忆化搜索用二维矩阵f[i][j]抽象为队列中数的个数为i,栈中数的个数为j的方案数.

那么对于f[i][j]这个状态可以变为
1.将状态1变为状态2,此时队列中有i-1个数栈中有j+1个数

2.当栈中有元素时(j>1)有状态2变为状态3即为选择一个数字出栈此时队列中有i个数,栈中有j-1个数

if(j>=1)f[i][j]+=dfs(i,j-1)
f[i][j]+=dfs(i-1,j+1)

当i=0,即为队列中所有数都入栈有且仅有一种出栈方式``
给出AC代码

#include<iostream>
using namespace std;
int n;
long long ans;
long long f[20][20];
long long dfs(int i,int j)
{
	if (f[i][j])return f[i][j];
	if (i == 0)return 1;
	if (j > 0)f[i][j] += dfs(i, j - 1);
	f[i][j] += dfs(i - 1, j + 1);
	if (j > 0)f[i][j] += dfs(i, j - 1);
	return f[i][j];

}
int main()
{
	cin >> n;
	cout<<dfs(n, 0);

	return 0;
}

解法二:递推

递推与递归想法截然相反,但又相似,我们需要考虑的是当前状态是由哪几种状态变化而来的,以及初始可确定的条件是哪些

同样关键的一步是用二维矩阵来表示方案数f[i][j]其中i表示栈中数的个数表示出栈数的个数

对于f[i][j]
1.由f[i][j-1]出栈一个数得到(状态2->3)(i-j>0)
2.由 f[i-1][j]入栈一个数得到(状态1->2)

#include<iostream>
using namespace std;
int n;
long long ans;
long long f[20][20];
int main()
{   
	cin >> n;
	for (int i = 0; i <= n; i++)
	{
		f[0][i] = 1;
	}
	for(int i=1;i<=n;i++)
		for (int j = i; j <= n; j++)
		{
			if (i == j)f[i][j] = f[i - 1][j];
			else f[i][j] = f[i - 1][j] + f[i][j - 1];
		}
	cout << f[n][n];
	return 0;
}

递归递推区别

这里讨论一下两种矩阵f[i][j]对于i和j意义为何有不同,我们来回顾一下两种算法中的i,j.
递归:二维矩阵f[i][j]来表示队列中数的个数为i,栈中数的个数为j的方案数.
递推:二维矩阵来表示方案数f[i][j]其中i表示栈中数的个数,j表示出栈数的个数

参数意义的不同与两种算法的思路有关,我们上面提到,递归考虑的是当前状态该如何变化到下一中状态,我们分析出对于每一个数有1->2->3这种唯一变化,将其拆分为1->2,2>3 两种情况所以对于递归我们应该使用的是状态1,与状态2 来进行变化,而递推则使用已确定的状态1与转态2,所以参数下标应该使用状态2与状态3.

对于该题如果数据较大的情况我们也可以使用卡特兰数公式,本文主要讲解递推与递归两种方法思想,给出链接供大家参考.
卡特兰数的证明与拓展