Count even length binary sequences with same sum of first and second half bits | A memoization based PHP program to count even length binary sequences such that the sum of first and second half bits is same ; A lookup table to store the results of subproblems ; dif is difference between sums of first n bits and last n bits i . e . , dif = ( Sum of first n bits ) - ( Sum of last n bits ) ; We can 't cover difference of more  than n with 2n bits ; n == 1 , i . e . , 2 bit long sequences ; Check if this subproblem is already solved n is added to dif to make sure index becomes positive ; $res = First bit is 0 & last bit is 1 ; First and last bits are same ; First bit is 1 & last bit is 0 ; Store result in lookup table and return the result ; A Wrapper over countSeqUtil ( ) . It mainly initializes lookup table , then calls countSeqUtil ( ) ; call countSeqUtil ( ) ; Driver Code
< ? php $ MAX = 1000 ; $ lookup = array_fill ( 0 , $ MAX , array_fill ( 0 , $ MAX , -1 ) ) ; function countSeqUtil ( $ n , $ dif ) { global $ lookup ; if ( abs ( $ dif ) > $ n ) return 0 ; if ( $ n == 1 && $ dif == 0 ) return 2 ; if ( $ n == 1 && abs ( $ dif ) == 1 ) return 1 ; if ( $ lookup [ $ n ] [ $ n + $ dif ] != -1 ) return $ lookup [ $ n ] [ $ n + $ dif ] ; countSeqUtil ( $ n - 1 , $ dif + 1 ) + 2 * countSeqUtil ( $ n - 1 , $ dif ) + countSeqUtil ( $ n - 1 , $ dif - 1 ) ; return $ lookup [ $ n ] [ $ n + $ dif ] = $ res ; } function countSeq ( $ n ) { return countSeqUtil ( $ n , 0 ) ; } $ n = 2 ; echo " Count ▁ of ▁ sequences ▁ is ▁ " . countSeq ( $ n ) ; ? >