Sequences of given length where every element is more than or equal to twice of previous | DP based function to find the number of special sequence ; define T and build in bottom manner to store number of special sequences of length n and maximum value m ; Base case : If length of sequence is 0 or maximum value is 0 , there cannot exist any special sequence ; if length of sequence is more than the maximum value , special sequence cannot exist ; If length of sequence is 1 then the number of special sequences is equal to the maximum value For example with maximum value 2 and length 1 , there can be 2 special sequences { 1 } , { 2 } ; otherwise calculate ; Driver Code
def getTotalNumberOfSequences ( m , n ) : NEW_LINE INDENT T = [ [ 0 for i in range ( n + 1 ) ] for i in range ( m + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if i == 0 or j == 0 : NEW_LINE INDENT T [ i ] [ j ] = 0 NEW_LINE DEDENT elif i < j : NEW_LINE INDENT T [ i ] [ j ] = 0 NEW_LINE DEDENT elif j == 1 : NEW_LINE INDENT T [ i ] [ j ] = i NEW_LINE DEDENT else : NEW_LINE INDENT T [ i ] [ j ] = T [ i - 1 ] [ j ] + T [ i // 2 ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT return T [ m ] [ n ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT m = 10 NEW_LINE n = 4 NEW_LINE print ( ' Total ▁ number ▁ of ▁ possible ▁ sequences ▁ ' , getTotalNumberOfSequences ( m , n ) ) NEW_LINE DEDENT