就是卡特兰数 ans=c[2n][n]-c[2n][n-1]
这里用递推的方法做
f[n][m]存储 n个进栈m个出栈的所有可能数
那么对于最后一个入栈的元素 我们将其分解成出栈与不出栈两种情况
若不出栈 则=f[n][m-1] 若出栈 则=f[n-1][m]
合在一起 就是fs[n][m]=f(n-1,m)+f(n,m-1);
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
int n;
ll fs[2010][2010];//fs存f(n,m)的答案
ll f(int n,int m){//求n个元素进栈 m个元素出栈有多少种情况的函数
//n<m 不符合定义
if (n<m) return 0;
//m=0无序列=0
if (m==0) {
fs[n][m]=1;
return 1;
}
if (!fs[n][m]) {//记忆化搜索降低复杂度
fs[n][m]=f(n-1,m)+f(n,m-1);
//对于最后一个入栈的元素 我们将其分解成出栈与不出栈两种情况
return fs[n][m];
}
return fs[n][m];
}
int main () {
cin>>n;
cout<<f(n,n);
return 0;
}