Count of binary strings of length N with even set bit count and at most K consecutive 1 s | Python3 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
import numpy as np NEW_LINE dp = np . ones ( ( ( 100002 , 21 , 3 ) ) ) NEW_LINE dp = - 1 * dp NEW_LINE def possibleBinaries ( pos , ones , sum , k ) : NEW_LINE INDENT if ( ones == k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( pos == 0 ) : NEW_LINE INDENT return 1 if ( sum == 0 ) else 0 NEW_LINE DEDENT if ( dp [ pos ] [ ones ] [ sum ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ ones ] [ sum ] NEW_LINE DEDENT ret = ( possibleBinaries ( pos - 1 , ones + 1 , ( sum + 1 ) % 2 , k ) + possibleBinaries ( pos - 1 , 0 , sum , k ) ) NEW_LINE dp [ pos ] [ ones ] [ sum ] = ret NEW_LINE return dp [ pos ] [ ones ] [ sum ] NEW_LINE DEDENT N = 3 NEW_LINE K = 2 NEW_LINE print ( int ( possibleBinaries ( N , 0 , 0 , K ) ) ) NEW_LINE