栈的输出序列与卡特兰数

栈的输出序列与卡特兰数从记忆化搜索到数学模型的深度解析在算法竞赛中经常会遇到关于合法操作序列计数的问题。以经典的洛谷 P1044 [NOIP 2003 普及组] 栈 为例题目要求计算1,2,…,n1,2,\ldots,n1,2,…,n经过栈的 push 和 pop 操作后可能得到的输出序列总数。本文将从基础的搜索状态空间出发探讨如何通过操作的唯一性进行计数并逐步引出这类问题的核心数学模型——卡特兰数Catalan Number同时深入解析卡特兰数在不同场景下的两种核心“面孔”。一、 基于过程的状态空间搜索与一一映射在面对“求合法结果的总数”时直接去枚举最终的排列并判断其合法性通常是困难且低效的。一个更底层的思维方式是不关注最终结果而是关注生成结果的操作过程。因为输入序列1,2,…,n1, 2, \ldots, n1,2,…,n的顺序是固定的任何一种合法的“进栈、出栈的操作序列”必然唯一对应一种“输出序列”。这就形成了一种一一映射的关系合法的操作序列数量等于合法的输出排列数量。因此可以通过深度优先搜索DFS模拟这个过程。在任意时刻状态可以由两个量唯一确定stknum: 当前栈内元素的个数。numbers: 还没入栈的元素个数。在任意状态下面临的合法决策最多只有两种进栈操作只要还有未入栈的元素numbers 0就可以将一个元素压入栈中此时stknum 1numbers - 1。出栈操作只要栈内有元素stknum 0就可以将栈顶元素弹出此时stknum - 1numbers不变。为了避免重复计算可以引入一个二维数组记录已经计算过的状态这就是记忆化搜索。以下是这种思路的 C 代码实现#includebits/stdc.husingnamespacestd;intn;intmem[30][30];intdfs(intstknum,intnumbers){// 边界条件如果没有未进栈的数字了剩余的元素只能依次全部出栈这构成 1 种确定方案if(numbers0){return1;}intcnt0;// 决策1将一个未入栈的数字压入栈中if(mem[stknum1][numbers-1]){cntmem[stknum1][numbers-1];}else{inttmpdfs(stknum1,numbers-1);cnttmp;mem[stknum1][numbers-1]tmp;}// 决策2将栈顶元素弹出前提是栈不为空if(stknum0){if(mem[stknum-1][numbers]){cntmem[stknum-1][numbers];}else{inttmpdfs(stknum-1,numbers);cnttmp;mem[stknum-1][numbers]tmp;}}returncnt;}intmain(){cinn;intcntdfs(0,n);coutcnt\n;return0;}上述代码的时间复杂度为O(n2)O(n^2)O(n2)对于n≤18n \le 18n≤18的数据范围绰绰有余。但如果nnn的范围扩大到10510^5105这种二维状态的递推将无法承受时间和空间的开销。二、 抽象为数学模型卡特兰数如果仔细观察上述搜索过程的核心限制整个过程需要执行nnn次进栈动作和nnn次出栈动作且在任何时刻已经执行的出栈次数绝对不能超过已经执行的进栈次数否则就会试图从空栈中弹出元素。在组合数学中满足这种“两种动作数量相等且在任意前缀中一种动作的数量不小于另一种动作的数量”的模型其合法方案总数构成了一个著名的数列——卡特兰数Catalan Number。卡特兰数的前几项为1,1,2,5,14,42,132…1, 1, 2, 5, 14, 42, 132 \dots1,1,2,5,14,42,132…对应n0,1,2,3,4,5,6…n0, 1, 2, 3, 4, 5, 6 \dotsn0,1,2,3,4,5,6…。三、 卡特兰数的两副“面孔”经典同构问题解析卡特兰数在数学和算法中有极其广泛的应用。表面上看毫不相干的问题背后往往隐藏着相同的数学本质。卡特兰数主要有两副核心“面孔”。面孔一两种操作互不超越线性匹配匹配除了栈的输出序列网格路径问题是这一面孔的经典代表在n×nn \times nn×n的网格中从左下角坐标(0,0)(0,0)(0,0)走到右上角(n,n)(n,n)(n,n)每次只能向右或向上走且不能越过对角线有多少种走法乍一看这与进出栈毫无关系。但细细剖析每次向右走一步横坐标xxx加 1每次向上走一步纵坐标yyy加 1。核心条件是“不能越过对角线”。对角线方程为yxy xyx不能越过意味着在整个行走的任意时刻必须满足y≤xy \le xy≤x。也就是说向上走的步数绝对不能超过向右走的步数。这与栈的操作完美对应向右走横坐标 1等价于进栈操作栈内元素 1向上走纵坐标 1等价于出栈操作栈内元素 -1不能越过对角线 (y≤xy \le xy≤x)等价于出栈的次数不能超过进栈的次数总共走到(n,n)(n,n)(n,n)等价于总共进行了nnn次进栈和nnn次出栈同理经典的括号匹配问题右括号数量不能超过左括号也完全契合这一模型。面孔二分治与组合的二叉树结构递归切分卡特兰数的另一副面孔体现在“将一个大问题切分成两个独立的小问题”的结构中。凸多边形划分问题是最佳代表将一个凸n2n2n2边形通过不相交的对角线划分为nnn个三角形有多少种划分方法这里似乎只有“画对角线”一种操作为什么也是卡特兰数假设有一个凸n2n2n2边形顶点按顺时针编号为1,2,3,…,n21, 2, 3, \ldots, n21,2,3,…,n2。我们可以盯住其中一条固定的边比如连接顶点111和n2n2n2的底边。在任何一种合法的三角形划分中这条底边必定属于某一个三角形。要构成这个三角形还需要选择第三个顶点kkkkkk可以是2,3,…,n12, 3, \ldots, n12,3,…,n1中的任意一个。一旦选定了这个顶点kkk大三角形(1,k,n2)(1, k, n2)(1,k,n2)就像一把刀把原来的多边形切成了两半左边由顶点1,2,…,k1, 2, \ldots, k1,2,…,k构成的一个凸kkk边形。右边由顶点k,k1,…,n2k, k1, \ldots, n2k,k1,…,n2构成的一个凸n3−kn3-kn3−k边形。这两个小多边形接下来还要各自继续划分三角形。如果定义HnH_nHn​为划分n2n2n2边形的方案数选定顶点kkk时的总划法就是左边的方案数乘上右边的方案数。把所有可能的kkk累加起来就得到了卡特兰数极其重要的非线性递推公式卷积公式HnH0Hn−1H1Hn−2H2Hn−3…Hn−1H0H_n H_0 H_{n-1} H_1 H_{n-2} H_2 H_{n-3} \ldots H_{n-1} H_0Hn​H0​Hn−1​H1​Hn−2​H2​Hn−3​…Hn−1​H0​进出栈问题同样可以用这个公式解释如果关注“最后一次出栈的元素是哪一个”也能将操作序列劈成左右两个互相独立的合法子序列从而推导出完全相同的乘法递推式。两种面孔在数学上殊途同归。四、 卡特兰数的求解公式与代码通过组合数学的反射容斥原理可以推导出卡特兰数HnH_nHn​的通项公式与线性递推公式。1. 组合数通项公式Hn1n1(2nn)(2n)!(n1)!n!H_n \frac{1}{n1} \binom{2n}{n} \frac{(2n)!}{(n1)!n!}Hn​n11​(n2n​)(n1)!n!(2n)!​2. 线性递推公式最常用于编程求解HnHn−1×4n−2n1H_n H_{n-1} \times \frac{4n - 2}{n 1}Hn​Hn−1​×n14n−2​利用递推公式可以在O(n)O(n)O(n)的时间复杂度与O(1)O(1)O(1)的空间复杂度下解决该问题完美突破搜索算法的瓶颈。#includeiostreamusingnamespacestd;intmain(){intn;cinn;// 使用 long long 防止乘法过程溢出longlongh1;for(inti1;in;i){hh*(4*i-2)/(i1);}couth\n;return0;}五、 结语解决合法操作计数问题时从状态空间搜索入手是一种非常直观且不易遗漏的思路。通过定义清晰的状态和合法的决策分支可以利用记忆化搜索或动态规划得到正确的答案。而当问题可以抽象为两种互相制约的操作或具备递归切分的二叉树特征时将其识别为卡特兰数模型则可以将算法的时间复杂度进一步降至线性级别这充分体现了数学抽象与算法结合的优雅之处。