Author: loop3r
Date: 20260224
tag: 递推
link: https://www.luogu.com.cn/problem/P1044

问题描述

link

分析

设 $h[i]$ 表示 $i$ 个元素的出栈方案数。对于每个元素而言，都可能是最后一个出栈的。假设第 $j$ 个元素是最后一个出栈的，比 $j$ 早入栈且早出栈的元素有 $j-1$ 个，一共有 $h[j-1]$ 种出栈方案；比 $j$ 晚入栈且早出栈的元素有 $n-j$ 个，一共有 $h[n-j]$ 种出栈方案，在这种情况下 $h[j]=h[j-1]\ast h[n-j]$。因此：$h[i]=\sum _{j=1}^{i}h[j-1]\ast h[i-j]$，边界条件：$h[0]=1,h[1]=1$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, h[20] = {1, 1};
    cin >> n;

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            h[i] += h[j - 1] * h[i - j];
        }
    }

    cout << h[n] << endl;

    return 0;
}