Non | A dynamic programming based function to find nth Catalan number ; Initialize first two values in table ; 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
< ? php function catalanDP ( $ n ) { $ catalan [ 0 ] = $ catalan [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { $ catalan [ $ i ] = 0 ; for ( $ j = 0 ; $ j < $ i ; $ j ++ ) $ catalan [ $ i ] += $ catalan [ $ j ] * $ catalan [ $ i - $ j - 1 ] ; } return $ catalan [ $ n ] ; } function countWays ( $ n ) { if ( $ n & 1 ) { echo " Invalid " ; return 0 ; } return catalanDP ( $ n / 2 ) ; } echo countWays ( 6 ) , " " ; ? >