Sum of Digits of the Good Strings | C ++ implementation of the approach ; To store the states of the dp ; Function to fill the dp table ; 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 ; Adjacent digits are different ; Increment the count as digit at ( i - 1 ) 'th index is k and count  of good strings is equal to this  because at the end of the strings of  length (i - 1) we are just  putting digit j as the last digit ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define DIGITS  10 NEW_LINE #define MAX  10000 NEW_LINE #define MOD  1000000007 NEW_LINE long dp [ MAX ] [ DIGITS ] , cnt [ MAX ] [ DIGITS ] ; void precompute ( ) { 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 ++ ) { if ( j != k ) { dp [ i ] [ j ] = dp [ i ] [ j ] + ( dp [ i - 1 ] [ k ] + ( cnt [ i - 1 ] [ k ] * j ) % MOD ) % MOD ; dp [ i ] [ j ] %= MOD ; cnt [ i ] [ j ] += cnt [ i - 1 ] [ k ] ; cnt [ i ] [ j ] %= MOD ; } } } } } int main ( ) { long long int x = 6 , y = 4 ; precompute ( ) ; cout << dp [ x ] [ y ] ; return 0 ; }