Count binary strings with k times appearing adjacent two set bits | PHP program to count number of binary strings with k times appearing consecutive 1 's. ; dp [ i ] [ j ] [ 0 ] stores count of binary strings of length i with j consecutive 1 ' s ▁ and ▁ ending ▁ at ▁ 0 . ▁ ▁ dp [ i ] [ j ] [1 ] ▁ stores ▁ count ▁ of ▁ binary ▁ ▁ strings ▁ of ▁ length ▁ i ▁ with ▁ j ▁ consecutive ▁ ▁ 1' s and ending at 1. ; If n = 1 and k = 0. ; number of adjacent 1 's can not exceed i-1 ; Driver code
< ? php function countStrings ( $ n , $ k ) { $ dp = array_fill ( 0 , $ n + 1 , array_fill ( 0 , $ k + 1 , array_fill ( 0 , 2 , 0 ) ) ) ; $ dp [ 1 ] [ 0 ] [ 0 ] = 1 ; $ dp [ 1 ] [ 0 ] [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { if ( isset ( $ dp [ $ i ] [ $ j ] [ 0 ] ) || isset ( $ dp [ $ i ] [ $ j ] [ 1 ] ) ) { $ dp [ $ i ] [ $ j ] [ 0 ] = $ dp [ $ i - 1 ] [ $ j ] [ 0 ] + $ dp [ $ i - 1 ] [ $ j ] [ 1 ] ; $ dp [ $ i ] [ $ j ] [ 1 ] = $ dp [ $ i - 1 ] [ $ j ] [ 0 ] ; } if ( $ j - 1 >= 0 && isset ( $ dp [ $ i ] [ $ j ] [ 1 ] ) ) $ dp [ $ i ] [ $ j ] [ 1 ] += $ dp [ $ i - 1 ] [ $ j - 1 ] [ 1 ] ; } } return $ dp [ $ n ] [ $ k ] [ 0 ] + $ dp [ $ n ] [ $ k ] [ 1 ] ; } $ n = 5 ; $ k = 2 ; echo countStrings ( $ n , $ k ) ; ? >