Python 计算第 n 个卡特兰数并取模 - 动态规划实现

以下是使用动态规划方法计算第 n 个卡特兰数并对模数取模的 Python 代码：

def catalan_number(n, mod=1000000000):
    if n == 0:
        return 1
    c = [0] * (n + 1)
    c[0] = 1
    for i in range(1, n + 1):
        for j in range(i):
            c[i] = (c[i] + c[j] * c[i - j - 1]) % mod
    return c[n]

该代码使用动态规划的方法求解卡特兰数，时间复杂度为 O(n^2)，空间复杂度为 O(n)。其中，c[i] 表示第 i 个卡特兰数，c[0]=1。对于 i，c[i] 的值由 c[0]~c[i-1] 的值递推得到。

该代码默认对 10 亿取模，可以根据需要修改 mod 参数的值来更改模数。例如，要对 100 取模，只需要将 catalan_number(n, mod=1000000000) 中的 mod 改为 100 即可。