Number of decimal numbers of length k , that are strict monotone | CPP 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
#include <cstring> NEW_LINE #include <iostream> NEW_LINE int static const DP_s = 9 ; int getNumStrictMonotone ( int len ) { int DP [ len ] [ DP_s ] ; memset ( DP , 0 , sizeof ( DP ) ) ; for ( int i = 0 ; i < DP_s ; ++ i ) DP [ 0 ] [ i ] = i + 1 ; for ( int i = 1 ; i < len ; ++ i ) for ( int 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 ] ; } int main ( ) { std :: cout << getNumStrictMonotone ( 2 ) ; return 0 ; }