Here's an implementation of finding the nth Catalan number in Python using dynamic programming:
main.py244 chars14 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.
gistlibby LogSnag