Number of decimal numbers of length k , that are strict monotone | PHP program to count numbers of k digits that are strictly monotone . ; DP [ i ] [ j ] is going to store monotone numbers of length i + 1 considering j + 1 digits ( 1 , 2 , 3 , . .9 ) ; Unit length numbers ; Building dp [ ] in bottom up ; Driver code
< ? php $ DP_s = 9 ; function getNumStrictMonotone ( $ len ) { global $ DP_s ; $ DP = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ len ; $ i ++ ) { for ( $ j = 0 ; $ j < $ DP_s ; $ j ++ ) $ DP [ $ i ] [ $ j ] = 0 ; } for ( $ i = 0 ; $ i < $ DP_s ; ++ $ i ) $ DP [ 0 ] [ $ i ] = $ i + 1 ; for ( $ i = 1 ; $ i < $ len ; ++ $ i ) for ( $ j = 1 ; $ j < $ DP_s ; ++ $ j ) $ DP [ $ i ] [ $ j ] = $ DP [ $ i - 1 ] [ $ j - 1 ] + $ DP [ $ i ] [ $ j - 1 ] ; return $ DP [ $ len - 1 ] [ $ DP_s - 1 ] ; } echo ( getNumStrictMonotone ( 2 ) ) ; ? >