Count N | Function to count binary strings of length N having substring "11" ; Initialize dp [ ] of size N + 1 ; Base Cases ; Stores the first N powers of 2 ; Generate ; Iterate over the range [ 2 , N ] ; Prtotal count of substrings ; Driver Code
def binaryStrings ( N ) : NEW_LINE INDENT dp = [ 0 ] * ( N + 1 ) NEW_LINE dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = 0 NEW_LINE power = [ 0 ] * ( N + 1 ) NEW_LINE power [ 0 ] = 1 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT power [ i ] = 2 * power [ i - 1 ] NEW_LINE DEDENT for i in range ( 2 , N + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ] + power [ i - 2 ] NEW_LINE DEDENT print ( dp [ N ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 12 NEW_LINE binaryStrings ( N ) NEW_LINE DEDENT