Count of binary strings of length N with even set bit count and at most K consecutive 1 s | C # program for the above approach ; Table to store solution of each subproblem ; Function to calculate the possible binary Strings ; If number of ones is equal to K ; pos : current position Base Case : When n length is traversed ; sum : count of 1 ' s ▁ ▁ Return ▁ the ▁ count ▁ ▁ of ▁ 1' s obtained ; If the subproblem has already been solved ; Return the answer ; Recursive call when current position is filled with 1 ; Recursive call when current position is filled with 0 ; Store the solution to this subproblem ; Driver Code ; Initialising the table with - 1
using System ; class GFG { static int [ , , ] dp = new int [ 100001 , 20 , 2 ] ; static int possibleBinaries ( int pos , int ones , int sum , int k ) { if ( ones == k ) return 0 ; if ( pos == 0 ) return ( sum == 0 ) ? 1 : 0 ; if ( dp [ pos , ones , sum ] != - 1 ) return dp [ pos , ones , sum ] ; int ret = possibleBinaries ( pos - 1 , ones + 1 , ( sum + 1 ) % 2 , k ) + possibleBinaries ( pos - 1 , 0 , sum , k ) ; dp [ pos , ones , sum ] = ret ; return dp [ pos , ones , sum ] ; } public static void Main ( String [ ] args ) { int N = 3 ; int K = 2 ; for ( int i = 0 ; i < 100001 ; i ++ ) { for ( int j = 0 ; j < 20 ; j ++ ) { for ( int l = 0 ; l < 2 ; l ++ ) dp [ i , j , l ] = - 1 ; } } Console . Write ( possibleBinaries ( N , 0 , 0 , K ) ) ; } }