Non | A dynamic programming based function to find nth Catalan number ; Table to store results of subproblems ; Fill entries in catalan [ ] using recursive formula ; Return last entry ; Returns count of ways to connect n points on a circle such that no two connecting lines cross each other and every point is connected with one other point . ; Throw error if n is odd ; Else return n / 2 'th Catalan number ; Driver Code
def catalanDP ( n ) : NEW_LINE INDENT catalan = [ 1 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT catalan [ i ] = 0 NEW_LINE 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 def countWays ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT print ( " Invalid " ) NEW_LINE return 0 NEW_LINE DEDENT return catalanDP ( n // 2 ) NEW_LINE DEDENT print ( countWays ( 6 ) ) NEW_LINE