Total number of non |  ; 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 wiint be dp [ 0 ] [ n ] + dp [ 1 ] [ n ] . . + dp [ 9 ] [ n ] ; Driver program
function countNonDecreasing ( n ) { let dp = new Array ( 10 ) ; for ( let i = 0 ; i < 10 ; i ++ ) { dp [ i ] = new Array ( n + 1 ) ; } for ( let i = 0 ; i < 10 ; i ++ ) { for ( let j = 0 ; j < n + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < 10 ; i ++ ) dp [ i ] [ 1 ] = 1 ; for ( let digit = 0 ; digit <= 9 ; digit ++ ) { for ( let len = 2 ; len <= n ; len ++ ) { for ( let x = 0 ; x <= digit ; x ++ ) dp [ digit ] [ len ] += dp [ x ] [ len - 1 ] ; } } let count = 0 ; for ( let i = 0 ; i < 10 ; i ++ ) count += dp [ i ] [ n ] ; return count ; } let n = 3 ; document . write ( countNonDecreasing ( n ) ) ;