题解：P1044 [NOIP 2003 普及组] 栈

· · 题解

题解：P1044 [NOIP 2003 普及组] 栈

题意简述

给定数字序列 1, 2, \ldots, n，通过栈的 push 和 pop 操作，求可能得到的所有输出序列的总数。

题目分析

本题属于组合数学问题，关键在于理解栈操作序列与卡塔兰数（Catalan numbers）之间的关系。对于一个长度为 n 的输入序列，其合法的栈操作序列数量即为第 n 个卡塔兰数。

卡塔兰数性质

卡塔兰数 C_n 满足以下递推关系：

C_n = \sum_{i=0}^{n-1} C_i \times C_{n-1-i} \quad \text{其中} \quad C_0 = 1

闭合形式为：

C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!(n+1)!}

算法选择

由于 n \leq 18，可以采用动态规划的方法计算卡塔兰数，时间复杂度为 O(n^2)。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int dp[20]={0};
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            dp[i]+=dp[j]*dp[i-j-1];
        }
    }
    cout<<dp[n];
    return 0;
}

复杂度分析