Count N | Python3 program for the above approach ; Function to count N digit numbers whose digits are less than or equal to the absolute difference of previous two digits ; If all digits are traversed ; If the state has already been computed ; If the current digit is 1 , any digit from [ 1 - 9 ] can be placed . If N == 1 , 0 can also be placed . ; If the current digit is 2 , any digit from [ 0 - 9 ] can be placed ; For other digits , any digit from 0 to abs ( prev1 - prev2 ) can be placed ; Return the answer ; Driver code ; Input ; Function call
dp = [ [ [ - 1 for i in range ( 10 ) ] for j in range ( 10 ) ] for k in range ( 50 ) ] NEW_LINE def countOfNumbers ( digit , prev1 , prev2 , N ) : NEW_LINE INDENT if ( digit == N + 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ digit ] [ prev1 ] [ prev2 ] != - 1 ) : NEW_LINE INDENT return dp [ digit ] [ prev1 ] [ prev2 ] NEW_LINE DEDENT dp [ digit ] [ prev1 ] [ prev2 ] = 0 NEW_LINE if ( digit == 1 ) : NEW_LINE INDENT term = 0 if N == 1 else 1 NEW_LINE for j in range ( term , 10 , 1 ) : NEW_LINE INDENT dp [ digit ] [ prev1 ] [ prev2 ] += countOfNumbers ( digit + 1 , j , prev1 , N ) NEW_LINE DEDENT DEDENT elif ( digit == 2 ) : NEW_LINE INDENT for j in range ( 10 ) : NEW_LINE INDENT dp [ digit ] [ prev1 ] [ prev2 ] += countOfNumbers ( digit + 1 , j , prev1 , N ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for j in range ( abs ( prev1 - prev2 ) + 1 ) : NEW_LINE INDENT dp [ digit ] [ prev1 ] [ prev2 ] += countOfNumbers ( digit + 1 , j , prev1 , N ) NEW_LINE DEDENT DEDENT return dp [ digit ] [ prev1 ] [ prev2 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE print ( countOfNumbers ( 1 , 0 , 0 , N ) ) NEW_LINE DEDENT