Friends Pairing Problem | Returns count of ways n people can remain single or paired up . ; Filling dp [ ] in bottom - up manner using recursive formula explained above . ; Driver code
< ? php function countFriendsPairings ( $ n ) { $ dp [ $ n + 1 ] = 0 ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) { if ( $ i <= 2 ) $ dp [ $ i ] = $ i ; else $ dp [ $ i ] = $ dp [ $ i - 1 ] + ( $ i - 1 ) * $ dp [ $ i - 2 ] ; } return $ dp [ $ n ] ; } $ n = 4 ; echo countFriendsPairings ( $ n ) ; ? >