Counting numbers of n digits that are monotone | PHP program to count numbers of n digits that are monotone . ; Considering all possible digits as { 1 , 2 , 3 , . .9 } ; DP [ i ] [ j ] is going to store monotone numbers of length i + 1 considering j + 1 digits . ; Unit length numbers ; Single digit numbers ; Filling rest of the entries in bottom up manner . ; Driver code
< ? php function getNumMonotone ( $ len ) { $ DP_s = 9 ; $ DP = array ( array_fill ( 0 , $ len , 0 ) , array_fill ( 0 , $ len , 0 ) ) ; for ( $ i = 0 ; $ i < $ DP_s ; ++ $ i ) $ DP [ 0 ] [ $ i ] = $ i + 1 ; for ( $ i = 0 ; $ i < $ len ; ++ $ i ) $ DP [ $ i ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ len ; ++ $ i ) for ( $ j = 1 ; $ j < $ DP_s ; ++ $ j ) $ DP [ $ i ] [ $ j ] = $ DP [ $ i - 1 ] [ $ j ] + $ DP [ $ i ] [ $ j - 1 ] ; return $ DP [ $ len - 1 ] [ $ DP_s - 1 ] ; } echo getNumMonotone ( 10 ) ; ? >