Find the number of binary strings of length N with at least 3 consecutive 1 s | Javascript implementation of the above approach ; Function to return the count of required strings ; '0' at ith position ; '1' at ith position ; Driver code ; Base condition : 2 ^ ( i + 1 ) because of 0 indexing
var n ; function solve ( i , x , dp ) { if ( i < 0 ) { return x == 3 ? 1 : 0 ; } if ( dp [ i ] [ x ] != - 1 ) { return dp [ i ] [ x ] ; } dp [ i ] [ x ] = solve ( i - 1 , 0 , dp ) ; dp [ i ] [ x ] += solve ( i - 1 , x + 1 , dp ) ; return dp [ i ] [ x ] ; } n = 4 ; var dp = Array ( n ) . fill ( ) . map ( ( ) => Array ( 4 ) . fill ( 0 ) ) ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < 4 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } for ( i = 0 ; i < n ; i ++ ) { dp [ i ] [ 3 ] = ( 1 << ( i + 1 ) ) ; } document . write ( solve ( n - 1 , 0 , dp ) ) ;