【NOIP真题】2003 栈 luogu-P1044 | 适用于

洛谷 P1044 这道栈题，输入 n 求合法出栈序列总数。n=3 时答案是 5。

这其实是在考卡特兰数。文章给的推荐解法是一维卷积递推：设 h[i] 为 i 个元素的方案数，枚举谁最后出栈，左右两部分独立相乘再相加。

状态转移就一条式子：h[i] = Σ(h[j] * h[i-1-j])。边界得设 h[0]=1，不然后面全算成 0；数组开 long long，别用局部变长数组。

二维 DP 也能做，但一维更短更快，考场首选。