题目背景

卡特兰数(Catalan Number)，是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。卡特兰数列的前几项是1，1，2，5，14，42……

设h(i)为卡特兰数的第i项，边界条件是h(0)=1，h(1)=1，

其余项，卡特兰数列满足递推式：h(i) = h(0) * h(i-1) + h(1) * h(i-2) + ... + h(i-1) * h(0), (i≥2)

例如当i=4时，h(4)= h(0) * h(3) + h(1) * h(2) + h(2) * h(1) + h(3) * h(0)，即h(0)~h(i-1)交叉相乘后求和（如图）。

题目描述

输入一个整数，计算卡特兰数列的第n项（左起第n个数）。

一个整数n(n≤20)。

一个整数代表为卡特兰数列的第n项（左起第n个数）。

时间1000ms，内存256MiB