求状态数

aimisiyou

已知n个1和n个-1组成一个序列，要求序列满足以下规则：
1、第一项必须为1；
2、最后一项必须为-1；
3、从第一项开始，任意1~K(1<=K<=N)项的和不能小于0.
求满足以上三条规则的序列的总个数。

显然，n=1时有（1，-1），即满足要求的序列个数为1；
n=2时有（1，1，-1，-1）和（1，-1，1，-1），即满足要求的序列个数为2；
……
f(n)=?

tzfcn

我认为至少有2n*(2n-1)种可能，如何优化算法很重要

aimisiyou

tzfcn 发表于 2020-5-22 14:06
我认为至少有2n*(2n-1)种可能，如何优化算法很重要

经群友提醒，可以看成括号配对问题（这个就很好理解了），实质就是卡特兰数。