Python编程题求助

Question

如题所述

Answer 1

该答案为组合数学中著名的卡特兰数，其通式为C(2n,n)-C(2n,n-1)

这里采用递推关系求解，即动态规划的方法

设n对父子有d[n]种出场策略，注意初值d[0]=1

因为每个孩子前面必有一个父亲与之对应

对于i对父子，遍历第j个孩子，该孩子前面有j-1个孩子，对应d[j-1]种出场策略

后面有i-j个孩子，对应d[i-j]种出场策略，则d[i]+=d[j-1]*d[i-j]，最终d[n]即为所求

python代码如下：

n = int(input())

d = [0] * (n+1)

d[0] = 1

for i in range(n+1):

    for j in range(i+1):

        d[i] += d[j-1] * d[i-j]

print(d[n])

运行结果如下：

望采纳~