Count of numbers upto N having absolute difference of at most K between any two adjacent digits | Table to store solution of each subproblem ; Function to calculate all possible numbers ; Check if position reaches end that is equal to length of N ; Check if the result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is false , means number has already become smaller so we can place any digit , otherwise N [ pos ] ; Chekc if start is false the number has not started yet ; Check if we do not start the number at pos then recur forward ; If we start the number we can place any digit from 1 to upper_limit ; Finding the new tight ; Condition if the number has already started ; We can place digit upto upperbound & absolute difference with previous digit much be atmost K ; Absolute difference atmost K ; Store the solution to this subproblem ; Driver code ; Function call
dp = [ [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 2 ) ] for i in range ( 10 ) ] for j in range ( 1002 ) ] NEW_LINE def possibleNumber ( pos , previous , tight , start , N , K ) : NEW_LINE INDENT if ( pos == len ( N ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ pos ] [ previous ] [ tight ] [ start ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ previous ] [ tight ] [ start ] NEW_LINE DEDENT res = 0 NEW_LINE if ( tight ) : NEW_LINE INDENT upper_limit = ord ( N [ pos ] ) - ord ( '0' ) NEW_LINE DEDENT else : NEW_LINE INDENT upper_limit = 9 NEW_LINE DEDENT if ( not start ) : NEW_LINE INDENT res = possibleNumber ( pos + 1 , previous , False , False , N , K ) NEW_LINE for i in range ( 1 , upper_limit + 1 ) : NEW_LINE INDENT if ( tight and i == upper_limit ) : NEW_LINE INDENT new_tight = 1 NEW_LINE DEDENT else : NEW_LINE INDENT new_tight = 0 NEW_LINE DEDENT res += possibleNumber ( pos + 1 , i , new_tight , True , N , K ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for i in range ( upper_limit + 1 ) : NEW_LINE INDENT if ( tight and i == upper_limit ) : NEW_LINE INDENT new_tight = 1 NEW_LINE DEDENT else : NEW_LINE INDENT new_tight = 0 NEW_LINE DEDENT if ( abs ( i - previous ) <= K ) : NEW_LINE INDENT res += possibleNumber ( pos + 1 , i , new_tight , True , N , K ) NEW_LINE DEDENT DEDENT DEDENT dp [ pos ] [ previous ] [ tight ] [ start ] = res NEW_LINE return dp [ pos ] [ previous ] [ tight ] [ start ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = "20" NEW_LINE K = 2 NEW_LINE print ( possibleNumber ( 0 , 0 , True , False , N , K ) ) NEW_LINE DEDENT