Calculate all states For every state , from numbers 1 to N , the count of numbers which contain exactly j non zero digits is being computed and updated in the dp array .
for ( int i = 0 ; i < n ; ++ i ) { int sm = 0 ; while ( sm < 2 ) { for ( int j = 0 ; j < k + 1 ; ++ j ) { int x = 0 ; while ( x <= ( sm ? 9 : s [ i ] - '0' ) ) { dp [ i + 1 ] [ sm || x < ( s [ i ] - '0' ) ] [ j + ( x > 0 ) ] += dp [ i ] [ sm ] [ j ] ; ++ x ; } } ++ sm ; } }