【数据结构与算法】进出栈方案数问题

进出栈方案数问题

让n个数字依次进栈,求不同的出栈序列的种类个数。

首先可以对问题进行一个转化,脱去数字本身的特性,单纯将出栈序列的序列看成是由进栈和出栈两种操作来构成的序列,其中我们可以令1代表入栈,0代表出栈。

而当出栈序列是非法的时候,就是在说栈为空时,仍然进行出栈操作,换成01串进行理解,也就是说,在整个01串中,存在某一个位置,且这个位置前面的操作0的个数大于1的个数,即说明这是非法的。

那么,我们要求出所有可行的方案,我们可以换一个角度。

合法方案数 = 总方案数 - 非法方案数

总方案数 = 给你2n个位置,先填入n个1,其他空余位置补上0 = \(C_{2n}^{n}\)

在计算非法方案数,我们可以稍微做一下转换。

(注意这里都是非法的,无论怎么转换的话)假设定在某个位置,这个位置前有p个1,p+1个0, 那么在这个位置后有n-p个1,n-(p+1)个0,在这里,我们可以稍微做一个转换,在这个位置后有n-p个"0",n-(p+1)个"1",所以此时2n个位置共有n+1个"0",n-1个"1"。

所以非法的方案数为\(C_{2n}^{n-1}\)

所以合法的方案数 = \(C_{2n}^{n}-C_{2n}^{n-1}\)

上一篇:CF1443A Kids Seating 题解


下一篇:算法设计与分析基础(三)