find the nth catalan number in python

Here's an implementation of finding the nth Catalan number in Python using dynamic programming:

main.py
def catalan(n):
    if n <= 1:
        return 1

    catalan = [0]*(n+1)
    catalan[0] = 1
    catalan[1] = 1

    for i in range(2, n+1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i-j-1]

    return catalan[n]
244 chars
14 lines

The function takes an integer n as input and returns the corresponding nth Catalan number. We first check if n is less than or equal to 1 as the Catalan number for n=0 and n=1 is 1. Then, we initialize an array of size n+1 with all zeroes and set catalan[0] and catalan[1] to 1.

Next, we iterate through i from 2 to n+1 and for each i, we iterate through j from 0 to i, and update catalan[i] as the sum of catalan[j] and catalan[i-j-1] multiplied together. We return the value of catalan[n] as the answer.

This implementation uses dynamic programming to store the values of Catalan numbers for smaller subproblems and avoids recalculating them.