Count of N | Python3 program for the above approach ; Function to count N - digit numbers having absolute difference between adjacent digits in non - increasing order ; If digit = n + 1 , a valid n - digit number has been formed ; If the state has already been computed ; If the current digit is 1 , then any digit from [ 1 - 9 ] can be placed ; If the current digit is 2 , any digit from [ 0 - 9 ] can be placed ; For other digits , any digit i can be placed which satisfies abs ( prev1 - i ) <= abs ( prev1 - prev2 ) ; If absolute difference is less than or equal to diff ; Function to count N - digit numbers with absolute difference between adjacent digits in non increasing order ; Initialize dp table with - 1 ; Function Call ; Driver code
dp = [ [ [ 0 for i in range ( 10 ) ] for col in range ( 10 ) ] for row in range ( 100 ) ] NEW_LINE def countOfNumbers ( digit , prev1 , prev2 , n ) : NEW_LINE INDENT if ( digit == n + 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT val = dp [ digit ] [ prev1 ] [ prev2 ] NEW_LINE if ( val != - 1 ) : NEW_LINE INDENT return val NEW_LINE DEDENT val = 0 NEW_LINE if ( digit == 1 ) : NEW_LINE INDENT i = 1 NEW_LINE if n == 1 : NEW_LINE INDENT i = 0 NEW_LINE DEDENT for j in range ( i , 10 ) : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , j , prev1 , n ) NEW_LINE DEDENT DEDENT elif ( digit == 2 ) : NEW_LINE INDENT for i in range ( 0 , 10 ) : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , i , prev1 , n ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT diff = abs ( prev2 - prev1 ) NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT if ( abs ( prev1 - i ) <= diff ) : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , i , prev1 , n ) NEW_LINE DEDENT DEDENT DEDENT return val NEW_LINE DEDENT def countNumbersUtil ( N ) : NEW_LINE INDENT for i in range ( 0 , 100 ) : NEW_LINE INDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT for k in range ( 0 , 10 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = - 1 NEW_LINE DEDENT DEDENT DEDENT print ( countOfNumbers ( 1 , 0 , 0 , N ) ) NEW_LINE DEDENT N = 3 NEW_LINE countNumbersUtil ( N ) NEW_LINE