Program for nth Catalan Number | A dynamic programming based function to find nth Catalan number ; Table to store results of subproblems ; Initialize first two values in table ; Fill entries in catalan [ ] using recursive formula ; Return last entry ; Driver code
def catalan ( n ) : NEW_LINE INDENT if ( n == 0 or n == 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT catalan = [ 0 ] * ( n + 1 ) NEW_LINE catalan [ 0 ] = 1 NEW_LINE catalan [ 1 ] = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT catalan [ i ] += catalan [ j ] * catalan [ i - j - 1 ] NEW_LINE DEDENT DEDENT return catalan [ n ] NEW_LINE DEDENT for i in range ( 10 ) : NEW_LINE INDENT print ( catalan ( i ) , end = " ▁ " ) NEW_LINE DEDENT