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

解题思路

把状态表示为“已经压入了多少个元素、已经弹出了多少个元素”。只有弹出数不超过压入数的状态才合法。f[i][j] 可由压入一个新元素的 f[i-1][j] 和弹出一个元素的 f[i][j-1] 转移。最终 f[n][n] 即卡特兰数。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

C++17 参考代码

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

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