codevs 1086_栈_dp

题目描述

将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。


思路

出栈方式其实就是一个卡特兰数,用dp公式推就可以了
f[i]表示深度为i的栈出栈方式数
f[i]=f[i-1]*(4*i-2)/(i+1)
O(n)


]]>