卡特兰数求解：递推公式、组合公式及代码示例

卡特兰数可以用递推公式或组合公式求解。对于递推公式，可以使用动态规划或递归算法。对于组合公式，可以使用公式法或生成函数法。

以下是使用动态规划求解第n个卡特兰数的代码：

def catalan(n, mod=10**9):
    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(1, n+1):
        for j in range(i):
            dp[i] += dp[j] * dp[i-j-1]
            dp[i] %= mod
    return dp[n]

n = int(input())
print(catalan(n))

以下是使用公式法求解第n个卡特兰数的代码：

from math import factorial

def catalan(n, mod=10**9):
    num = factorial(2*n) % mod
    den = factorial(n+1) * factorial(n) % mod
    return num * pow(den, mod-2, mod) % mod

n = int(input())
print(catalan(n))

对于较大的n，使用递推公式可能更快。如果需要求多个卡特兰数，可以预处理出前n个卡特兰数，然后直接查表。