Count number of ways to partition a set into k subsets | Returns count of different partitions of n elements in k subsets ; Table to store results of subproblems ; Base cases ; Fill rest of the entries in dp [ ] [ ] in bottom up manner ; Driver Code
< ? php function countP ( $ n , $ k ) { $ dp [ $ n + 1 ] [ $ k + 1 ] = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ dp [ $ i ] [ 0 ] = 0 ; for ( $ i = 0 ; $ i <= $ k ; $ i ++ ) $ dp [ 0 ] [ $ k ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) for ( $ j = 1 ; $ j <= $ i ; $ j ++ ) if ( $ j == 1 $ i == $ j ) $ dp [ $ i ] [ $ j ] = 1 ; else $ dp [ $ i ] [ $ j ] = $ j * $ dp [ $ i - 1 ] [ $ j ] + $ dp [ $ i - 1 ] [ $ j - 1 ] ; return $ dp [ $ n ] [ $ k ] ; } echo countP ( 5 , 2 ) ; ? >