Total number of non | Python3 program to count non - decreasing number with n digits ; dp [ i ] [ j ] contains total count of non decreasing numbers ending with digit i and of length j ; Fill table for non decreasing numbers of length 1. Base cases 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ; Fill the table in bottom - up manner ; Compute total numbers of non decreasing numbers of length 'len   ; sum of all numbers of length of len - 1 in which last digit x is <= 'digit   ; There total nondecreasing numbers of length n won 't be dp[0][n] +  dp[1][n] ..+ dp[9][n] ; Driver Code
def countNonDecreasing ( n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 1 ) ] for i in range ( 10 ) ] NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT dp [ i ] [ 1 ] = 1 NEW_LINE DEDENT for digit in range ( 10 ) : NEW_LINE INDENT for len in range ( 2 , n + 1 ) : NEW_LINE INDENT for x in range ( digit + 1 ) : NEW_LINE INDENT dp [ digit ] [ len ] += dp [ x ] [ len - 1 ] NEW_LINE DEDENT DEDENT DEDENT count = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT count += dp [ i ] [ n ] NEW_LINE DEDENT return count NEW_LINE DEDENT n = 3 NEW_LINE print ( countNonDecreasing ( n ) ) NEW_LINE