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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100001 ] [ 20 ] [ 2 ] ; 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 ] ; } int main ( ) { int N = 3 ; int K = 2 ; memset ( dp , -1 , sizeof dp ) ; cout << possibleBinaries ( N , 0 , 0 , K ) ; }