Count of Binary strings of length N having atmost M consecutive 1 s or 0 s alternatively exactly K times | List to contain the final result ; Function to get the number of desirable binary strings ; If we reach end of string and groups are exhausted , return 1 ; If length is exhausted but groups are still to be made , return 0 ; If length is not exhausted but groups are exhausted , return 0 ; If both are negative just return 0 ; If already calculated , return it ; Initialise answer for each state ; Loop through every possible m ; Driver code
rows , cols = ( 1000 , 1000 ) NEW_LINE dp = [ [ 0 for i in range ( cols ) ] for j in range ( rows ) ] NEW_LINE def solve ( n , k , m ) : NEW_LINE INDENT if n == 0 and k == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT if n == 0 and k != 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if n != 0 and k == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if n < 0 or k < 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ n ] [ k ] : NEW_LINE INDENT return dp [ n ] [ k ] NEW_LINE DEDENT ans = 0 NEW_LINE for j in range ( 1 , m + 1 ) : NEW_LINE INDENT ans = ans + solve ( n - j , k - 1 , m ) NEW_LINE DEDENT dp [ n ] [ k ] = ans NEW_LINE return dp [ n ] [ k ] NEW_LINE DEDENT N = 7 NEW_LINE K = 4 NEW_LINE M = 3 NEW_LINE print ( solve ( N , K , M ) ) NEW_LINE