Counting 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
DP_s = 9 NEW_LINE def getNumMonotone ( ln ) : NEW_LINE INDENT DP = [ [ 0 ] * DP_s for i in range ( ln ) ] NEW_LINE for i in range ( DP_s ) : NEW_LINE INDENT DP [ 0 ] [ i ] = i + 1 NEW_LINE DEDENT for i in range ( ln ) : NEW_LINE INDENT DP [ i ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , ln ) : NEW_LINE INDENT for j in range ( 1 , DP_s ) : NEW_LINE INDENT DP [ i ] [ j ] = DP [ i - 1 ] [ j ] + DP [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT return DP [ ln - 1 ] [ DP_s - 1 ] NEW_LINE DEDENT print ( getNumMonotone ( 10 ) ) NEW_LINE