出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
解法1——递归/记忆化搜索
- 考虑用一个二维数组f[i][j]模拟当前情况：i——进栈序列中还有i个待排的数，j——栈中有j个数，f[i][j]的值表示当前i,j情况下有几种输出方案。
- 首先如果f[i][j]有值，直接调用即可（记忆化搜索，节省时间）；
- 如果i=0，即序列全部入栈，只有一种输出方法，所以返回1；
- 考虑一般情况，有两种输出方案，先进一个再出，即加上f[i-1][j+1],（栈不空时,j>0,如果栈空只有第一种输出方案可行）直接出，即加上f[i][j-1]。
代码如下
long long f[MAX][MAX];
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);
return f[i][j];
}
int main()
{
int n;
scanf("%d", &n);
printf("%lld", dfs(n, 0));
return 0;
}
解法2——递推
- 首先重设一下f[i][j],f的含义不变，i为入栈数，j为出栈数；
- 我们知道f[0][j]=1，因为序列全部入栈，出栈次序是唯一的。
- 然后我们来考虑一下递归关系，如何得到f[i][j]?即怎么得到i个数入栈，j个数出栈的情况，只需要有i-1个数入栈，出栈j个，此时再入栈一个就是f[i][j]；同理，可以是i个数入栈，j-1个出栈。所以我们得到递归关系f[i][j]=f[i-1][j]+f[i][j-1]。
- 但涉及到出栈必须考虑栈空的情况，什么时候栈空？i=j时，就只有f[i][j]=f[i-1][j]。
递归做法
long long f[MAX_N][MAX_N];
int main()
{
int n;
scanf("%d",&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][j-1]+f[i-1][j];
}
}
printf("%lld",f[n][n]);
return 0;
}
解法3——卡特兰数
关于卡特兰数列的详细解释移步百度百科
- 我们可以直接用的是它的四个递推公式
设h(n)为catalan数的第n项，令h(0)=1,h(1)=1，catalan数满足递推式 ：
1)h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n≥2)
2)h(n)=h(n-1) * (4n-2)/(n+1)
3)h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
4)h(n)=C(2n,n) - C(2n,n-1) (n=0,1,2,…)
代码都有递推关系了代码不是有手就行
//给出公式4作为参照
long long c[MAX][MAX];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
{
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
printf("%lld",c[2*n][n]-c[2*n][n-1]);
return 0;
}
关键是分析为什么可以用卡特兰
- 原理分析：
- 建立数组f。f[i]表示i个数的全部可能性。
f[0] = 1, f[1] = 1; //当然只有一个
设 x 为当前出栈序列的最后一个，则x有n种取值
由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分
1.比x小
2.比x大
比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]
比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]
这两部分互相独立，所以根据乘法原理，一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
另外，由于x有n个取值，所以
ans = f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0]; - 或者这样分析：
- 我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。
那么合法序列就是总序列-非法序列，总序列(由n次出栈n次入栈操作构成的序列数)为C(2n,n)。
非法序列：由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
这就证明了不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。，为C(2n,n+1)
所以有输出序列的总数目=c(2n,n)-c(2n,n-1)=c(2n,n)/(n+1)=h(n)。
我觉得这类题目可以总结为由特定顺序（二者匹配）的两种状态组成的排序数类问题
类似题目有
括号序列 ：n 对括号，则有多少种 “括号匹配” 的括号序列
——左括号看作1，右括号看作0，和上题一样
二叉树n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树
（国际）满二叉树定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
——形成满二叉树需要先向左扩展，再向右扩展，左右匹配，所以向左看作1，向右看作0，n+1个叶子结点有2n次扩展，还原为出入栈
买票找零：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零
——拿5元的看作1，10元的看作0
所以要对这类题目有一定敏感性