栈 是 一 种 常 见 的 数 据 结 构 ， 有 许 多 关 于 栈 的 问 题 ， 其 中 之 一 就 是 统 计 元 素 可 能的 出 栈 序 列 。具体说， 就 是 给定 n个元 素 ， 依次通过一 个栈 ， 求可 能 的 出 栈 序列 的 个数 。 如果我们用直接模拟的 方法， 当 n较大时会很费时间； 例如动态规划。令 f[i,j]表示栈内有 i个元素且栈外有 j个元素还未进栈，那么以进栈还是出栈为决策就马上得到了转移方程 f[i,j]=f[i-1,j]+f[i+1,j-1]。如此一来，很多重复的计算得以免去，效率大幅提高（时间复杂度为指数级，大概为 N^２级的算法）。 另一 种 方法是 利用组合数 学求出 栈 序 列 个数 ， 得到公式 下面我们来看一 种 图形化的 方法证明这个等式， 很容易理解的 。 我们把对 n个元 素 的 n次进栈 和 n次出 栈 理解为在一 个 n * n的 方格中 向右走 n次（代表进栈 ）， 向上走 n次（代表出 栈 ）。由于 出 栈 次数 不能 大于 进栈 次数 ， 我们可 以得到这样一 个方格： 每次沿着实线走，所以，只要求出从方格左下角到右上角路径的个数即可。 我们把表格补全，考虑每一条不合法的路径，如 在这条路径上，必然有一个地方连续两次向上，即从图上蓝点处开始，而且这个点必然在如图所示的绿线上。我们以这个点为起点，把到左上角整条路经取反，也就是对称上去，得到一条新路径，但是超出了表格。我们知道，这条路径包括 n + 1 次向上和 n – 1 次向下，也就是在一个(n + 1 ) * (n - 1 )的方格中。由此我们知道，一条不合法路径必然对应一个(n + 1 ) * (n - 1 )方格中的路径。同样地，对于(n + 1 ) * (n - 1 )方格中任意一条路径，以这条路径与绿线的第一个交点为起点到方格的右上方全部取反，即可得到一个在 n * n 方格中的不合法路径。 我们通过这样的方法确定了每条不合法路径与一个(n + 1) * (n - 1)方格中路径的一一对应关系，因此，方格中不合法路径总数为C(2n, n - 1)，而所有路径总数为C(2n, n)，两式相减即为原组合等式。 解二： 出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 分析：对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1 和 n个0 组成的2n位二进制数。由于等待...
