#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]; 这，就是传说中的卡特兰数

直接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; }

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; }