Returns count of ways n people can remain single or paired up .
def countFriendsPairings ( n ) : NEW_LINE INDENT global dp NEW_LINE if ( dp [ n ] != - 1 ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT if ( n > 2 ) : NEW_LINE INDENT dp [ n ] = ( countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 ) ) NEW_LINE return dp [ n ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ n ] = n NEW_LINE return dp [ n ] NEW_LINE DEDENT DEDENT