Friends Pairing Problem | Returns count of ways n people can remain single or paired up . ; Driver Code
< ? php function countFriendsPairings ( $ n ) { $ dp = array_fill ( 0 , 1000 , -1 ) ; if ( $ dp [ $ n ] != -1 ) return $ dp [ $ n ] ; if ( $ n > 2 ) { $ dp [ $ n ] = countFriendsPairings ( $ n - 1 ) + ( $ n - 1 ) * countFriendsPairings ( $ n - 2 ) ; return $ dp [ $ n ] ; } else { $ dp [ $ n ] = $ n ; return $ dp [ $ n ] ; } } $ n = 4 ; echo countFriendsPairings ( $ n ) ? >