讨论 / 谁能严格证明一下这题为什么是卡特兰数?
nezharen 2013-10-02 10:25:00
点我顶贴 收藏 删除
rt
#1 lychees@2011-10-01 17:25:00
回复 删除
哪题= =
#2 nezharen@2011-10-03 17:56:00
回复 删除
第53道,栈。多谢大牛。
#3 GUA@2013-09-17 21:21:00
回复 删除
我一开始就那样想的

依次从i=1到n,已经把f[i-1]和f[n-i-1]算出来了嘛,那么先把左边移过去有f[i-1]种,在把第i位移过去,在把右边的移过去有f[n-i-1],所以,第i位有f[i-1]*f[n-i-1]这么多种,再累加就对了

#4 Happiness@2013-10-02 10:25:00
回复 删除
回复 地毯GUA 的帖子

DDDDD

大牛!

#5 shenhong000@2013-11-04 12:11:35
回复 删除
百度卡特兰数 然后你就会发现一个式子f[i]=f[0]*f[i-1]+f[1]*f[i-2]....+f[i-1]*f[0] 其实 这是表示1是第几个出栈的 把栈分成两段 一段是1~i 另一段是i+1~n 那么和 就是枚举i累加两段之积
查看更多回复
提交回复