Count L | Function to find the number of arrays of length L such that each element divides the next element ; Stores the number of sequences of length i that ends with j ; Base Case ; Iterate over the range [ 0 , l ] ; Iterate for all multiples of j ; Incrementing dp [ i + 1 ] [ k ] by dp [ i ] [ j ] as the next element is multiple of j ; Stores the number of arrays ; Add all array of length L that ends with i ; Return the resultant count ; Driver Code
def numberOfArrays ( n , l ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 1 ) ] for i in range ( l + 1 ) ] NEW_LINE dp [ 0 ] [ 1 ] = 1 NEW_LINE for i in range ( l ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT for k in range ( j , n + 1 , j ) : NEW_LINE INDENT dp [ i + 1 ] [ k ] += dp [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans += dp [ l ] [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N , L = 2 , 4 NEW_LINE print ( numberOfArrays ( N , L ) ) NEW_LINE DEDENT