#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }

动态规划(DPDPDP:DYNAMICDYNAMICDYNAMIC PROGRAMMINGPROGRAMMINGPROGRAMMING)解法 1.思路： 这道题一眼给我们的感觉就是方案数太多了，而且利用暴力DFS是可以解决的，但是效率太慢。此时我们就应该思考一下DP了。 (1) f(i,j)f(i,j)f(i,j)表示的是，队列中的有iii个元素，栈中有jjj个元素的时候，能够输出的栈序列总数。 (2) 状态转移 一般情况下，我们面临的只有两种方式： 要么让队列中的元素入栈:f(i−1,j+1)f(i-1,j+1)f(i−1,j+1) 要么就是让队列中的元素不动，栈中的元素出队。 所以方程是：f(i,j−1)f(i,j-1)f(i,j−1) (3)循环设计 循环的设计是为了保证每次利用状态转移方程求解问题的时候，方程右侧的子问题已经在此之前正确的求解。 如果说的高端一些，就是我们的循环设计要满足拓扑排序。 我们看方程： 在算f(i,j)f(i,j)f(i,j)的时候，我们要知道的子问题答案有： f(i−1,j+1)f(i-1,j+1)f(i−1,j+1)和f(i,j−1)f(i,j-1)f(i,j−1) 所以我们的外循环枚举iii,内循环枚举jjj。如果反过来的话，我们会发现，我们含j+1j+1j+1的那一项无法在此之前算出。 (4)初末状态 初始状态是为了初始化最小的子问题，末尾状态是为了表示我们的答案。 我们的初始状态即当栈中的元素是j个，队列中的元素是0个的时候，我们只能出栈。此时只有1种序列。 还有就是当我们的队列中的元素只有1个，我们的栈中元素的个数是0的时候，我们此时的序列也是只有一种。 我们的最终状态是，队列中的元素个数是n，栈中的元素个数是0。即f[n][0] AC代码

#include<bits/stdc++.h> using namespace std; int main(){ int b,a[1000]={1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452}; cin>>b; cout<<a[b]; return 0; }

本题的描述十分简单。n个数依次进栈，可随机出栈。求有几种可能。 dfs可以解，但是递推仿佛好像如同看上去貌似更简单一些。 解释一下原理： 建立数组f。f[i]表示i个数的全部可能性。 f[0] = 1, f[1] = 1; //当然只有一个 设 x 为当前出栈序列的最后一个，则x有n种取值 由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分 比x小 比x大 比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1] 比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x] 这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x] 另外，由于x有n个取值，所以 ans = f[0]*f[n-1] + f[1]*f[n-2] + ... + f[n-1]*f[0]; 这，就是传说中的卡特兰数

显然结果为第 nnn 个卡特兰数. 时间复杂度：O(n)O(n)O(n)

直接dfs

#include <cstdio> int n,f[30]; int main() { scanf("%d", &n); f[0]=1; f[1]=1; for(int i=2;i<=n;i++) for(int j=0;j<i;j++) f[i]+=f[j]*f[i-j-1]; printf("%d",f[n]); }

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

直接上代码也可以用<iostream>

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

//认真看，杜绝抄袭 //好好消化一下，这题很经典 //记忆化搜索/递归 做法 #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N][MAX_N]; ll dfs(int i,int j) { if(f[i][j]) return f[i][j]; if(i==0)return 1; //边界 if(j>0) f[i][j]+=dfs(i,j-1); f[i][j]+=dfs(i-1,j+1); return f[i][j]; } int main() { scanf("%d",&n); printf("%lld",dfs(n,0)); return 0; } //递归转递推 递推做法 #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N][MAX_N]; int main() { scanf("%d",&n); for(int i=0;i<=n;i++) { f[0][i]=1; } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { if(i==j)f[i][j]=f[i-1][j]; else f[i][j]=f[i][j-1]+f[i-1][j]; } } printf("%lld",f[n][n]); return 0; } //数论做法 卡特兰数 //公式1： #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N]; int main() { f[0]=f[1]=1; scanf("%d",&n); for(int i=2;i<=n;i++) { for(int j=0;j<i;j++) { f[i]+=f[j]*f[i-j-1]; } } printf("%lld",f[n]); return 0; } //公式2： #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N]; int main() { f[0]=f[1]=1; scanf("%d",&n); for(int i=2;i<=n;i++) { f[i]+=f[i-1](4i-2)/(i+1); } printf("%lld",f[n]); return 0; } //公式3： #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll c[MAX_N*2][MAX_N]; int main(){ } //公式4： #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll c[MAX_N*2][MAX_N]; int main(){ } //高精/打表： #include<iostream> #include<cstdio> #include<cstring> #define MAX_N 110 using namespace std; int f[MAX_N][MAX_N],c[MAX_N]; inline int len(int a[]) { int i; for(i=60;i>=0;i--)//想要100个以上，这个i的范围要改 { if(a[i]!=0) break; } return i; } inline void add(int a[],int b[],int w)//高精加法 { int lena=len(a),lenb=len(b); for(int i=0;i<=max(lena,lenb);i++) { f[w][i]=a[i]+b[i]; } for(int i=0;i<=max(lena,lenb)+1;i++) { f[w][i+1]+=f[w][i]/10; f[w][i]%=10; } } inline void Catalan(int a[],int b[])//卡特兰 { memset(c, 0, sizeof(c)); int lena=len(a),lenb=len(b); for (int i=0;i<=lena;i++){ for (int j=0;j<=lenb;j++) c[i+j]+=a[i]*b[j]; } for (int i=0;i<=lena+lenb+1;i++) { c[i+1]+=c[i]/10; c[i]%=10; } } int main() { //int k; freopen("Catalan.txt","w"stdin);//文件操作; f[0][0]=f[1][0]=1; for (int i=2;i<=100;i++)//同理，要多输出几个i就等于几 { for (int j=0;j<i;j++) { Catalan(f[j], f[i-j-1]); add(f[i],c,i); } } for(int i=1;i<=100;i++)//输出 卡特兰数 1-100，范围同上，要输出几个自己改 { for (int j=len(f[i]);j>=0;j--) { //printf("%d",f[i][j]); putchar((char)f[i][j]+'0');//比printf稍快? } printf("\n"); } return 0; } 虽然可能讲的不好，但是看我写了这么多，点个赞好吗？

#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }#include <cstdio> int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; }