思路

这道题要求计算通过栈操作可能得到的输出序列总数，本质上是计算卡特兰数。卡特兰数描述了n个元素按特定顺序进出栈所能得到的不同序列的数量。

卡特兰数性质

• 当n=0时，只有1种序列（空序列）

• 当n=1时，只有1种序列

• 对于n≥1，卡特兰数满足递推关系： Cn=∑i=0n−1Ci×Cn−1−iCn​=∑i=0n−1​Ci​×Cn−1−i​

动态规划解法

1. 定义dp[i]表示i个元素的出栈序列总数

2. 初始化dp = 1（空序列）

3. 对于每个i从1到n：

   • 枚举分割点k（0 ≤ k ≤ i-1）

   • 左部分有k个元素，右部分有i-1-k个元素

   • 累加dp[k] * dp[i-1-k]

4. 最终dp[n]即为所求

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> dp(n + 1, 0);
    
    // 初始状态：0个元素只有1种序列
    dp[0] = 1;
    
    // 计算从1到n的卡特兰数
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < i; ++k) {
            dp[i] += dp[k] * dp[i - 1 - k];
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}