Find the number of binary strings of length N with at least 3 consecutive 1 s | C ++ implementation of the 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n ; int solve ( int i , int x , int dp [ ] [ 4 ] ) { if ( i < 0 ) return x == 3 ; 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 ] ; } int main ( ) { n = 4 ; int dp [ n ] [ 4 ] ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < 4 ; j ++ ) dp [ i ] [ j ] = -1 ; for ( int i = 0 ; i < n ; i ++ ) { dp [ i ] [ 3 ] = ( 1 << ( i + 1 ) ) ; } cout << solve ( n - 1 , 0 , dp ) ; return 0 ; }