Sum of digits of the string of length 1 is i as i is only number in that string and count of good strings of length 1 that end with i is also 1
for ( int i = 0 ; i < DIGITS ; i ++ ) dp [ 1 ] [ i ] = i , cnt [ 1 ] [ i ] = 1 ; for ( int i = 2 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < DIGITS ; j ++ ) { for ( int k = 0 ; k < DIGITS ; k ++ ) {