透过现象看本质
对n个数进行入栈出栈操作,那么操作过程中一定会有n个入栈操作和n个出栈操作
如果把入栈出栈操作形成序列的话:一定会得到2n长的出栈入栈序列
并且不同的合法出栈序列一定对应着唯一的合法操作序列
什么是合法呢?操作序列的任意一个前缀序列中入栈操作数量一定大于等于出栈操作数
那么本题可以看作从(0,0)点走到(n,n)点的路径数,每一步只能向下或者向右走,向下表示入栈,向右表示出栈,
要求表中走的路径一定是x>=y的,则a[n][n]即为答案
a[i][j]=a[i-1][j]+a[i][j-1];
#include<bits/stdc++.h>
using namespace std;
const int N=18+5;
int a[N][N];
int main()
{
int n;
cin>>n;
a[0][0]=1;
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
{
if(i-1>=0&&i-1>=j)
a[i][j]+=a[i-1][j];
if(j-1>=0&&i>=j-1)
a[i][j]+=a[i][j-1];
}
cout<<a[n][n];
return 0;
}