Count strings with consecutive 1 's | Returns count of n length binary strings with consecutive 1 's ; Count binary strings without consecutive 1 's.  See the approach discussed on be  ( http:goo.gl/p8A3sW ) ; Subtract a [ n - 1 ] + b [ n - 1 ] from 2 ^ n ; Driver Code
< ? php function countStrings ( $ n ) { $ a [ $ n ] = 0 ; $ b [ $ n ] = 0 ; $ a [ 0 ] = $ b [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ a [ $ i ] = $ a [ $ i - 1 ] + $ b [ $ i - 1 ] ; $ b [ $ i ] = $ a [ $ i - 1 ] ; } return ( 1 << $ n ) - $ a [ $ n - 1 ] - $ b [ $ n - 1 ] ; } echo countStrings ( 5 ) , " STRNEWLINE " ; ? >