Total number of non | PHP 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 wiint be dp [ 0 ] [ n ] + dp [ 1 ] [ n ] . . + dp [ 9 ] [ n ] ; Driver program
< ? php function countNonDecreasing ( $ n ) { $ dp = array_fill ( 0 , 10 , array_fill ( 0 , $ n + 1 , NULL ) ) ; for ( $ i = 0 ; $ i < 10 ; $ i ++ ) $ dp [ $ i ] [ 1 ] = 1 ; for ( $ digit = 0 ; $ digit <= 9 ; $ digit ++ ) { for ( $ len = 2 ; $ len <= $ n ; $ len ++ ) { for ( $ x = 0 ; $ x <= $ digit ; $ x ++ ) $ dp [ $ digit ] [ $ len ] += $ dp [ $ x ] [ $ len - 1 ] ; } } $ count = 0 ; for ( $ i = 0 ; $ i < 10 ; $ i ++ ) $ count += $ dp [ $ i ] [ $ n ] ; return $ count ; } $ n = 3 ; echo countNonDecreasing ( $ n ) ; return 0 ; ? >