Count of strictly increasing N | Declaration of dp table ; Function to find the count of all N digit numbers such that all the digit is less than its adjacent digits ; Base Case : If i = n , then return 1 as valid number has been formed ; If the state has already been computed , then return it ; Stores the total count of ways for the current recursive call ; If i = 0 , any digit from [ 1 - 9 ] can be placed and also if N = 1 , then 0 can also be placed ; If i = 1 , any digit from [ 0 - 9 ] can be placed such that digit is not equal to previous digit ; If the current digit is not same as the prev ; Place the current digit such that it is less than the previous digit ; Place current digit such that it is more than the previous digit ; Return the resultant total count ; Function to find all N - digit numbers satisfying the given criteria ; Function call to count all possible ways ; Driver Code
dp = [ [ [ - 1 for x in range ( 2 ) ] for y in range ( 10 ) ] for z in range ( 100 ) ] NEW_LINE def solve ( i , n , prev , sign ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT val = dp [ i ] [ prev ] [ sign ] NEW_LINE if ( val != - 1 ) : NEW_LINE INDENT return val NEW_LINE DEDENT val = 0 NEW_LINE if ( i == 0 ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT digit = 0 NEW_LINE DEDENT else : NEW_LINE INDENT digit = 1 NEW_LINE DEDENT while digit <= 9 : NEW_LINE INDENT val += solve ( i + 1 , n , digit , sign ) NEW_LINE digit += 1 NEW_LINE DEDENT DEDENT elif ( i == 1 ) : NEW_LINE INDENT for digit in range ( 10 ) : NEW_LINE INDENT if ( digit != prev ) : NEW_LINE INDENT val += solve ( i + 1 , n , digit , ( digit > prev ) ) NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT if ( sign == 1 ) : NEW_LINE INDENT for digit in range ( prev - 1 , - 1 , - 1 ) : NEW_LINE INDENT val += solve ( i + 1 , n , digit , 0 ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for digit in range ( prev + 1 , 10 ) : NEW_LINE INDENT val += solve ( i + 1 , n , digit , 1 ) NEW_LINE DEDENT DEDENT DEDENT return val NEW_LINE DEDENT def countNdigitNumber ( N ) : NEW_LINE INDENT print ( solve ( 0 , N , 0 , 0 ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE countNdigitNumber ( N ) NEW_LINE DEDENT