Count of N | Function to return count of N - digit numbers with absolute difference of adjacent digits not exceeding K ; For 1 - digit numbers , the count is 10 ; dp [ i ] [ j ] stores the count of i - digit numbers ending with j ; Initialize count for 1 - digit numbers ; Compute values for count of digits greater than 1 ; Find the range of allowed numbers if last digit is j ; Perform Range update ; Prefix sum to find count of of i - digit numbers ending with j ; Stores the final answer ; Driver Code
def getCount ( n , k ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return 10 NEW_LINE DEDENT dp = [ [ 0 for x in range ( 11 ) ] for y in range ( n + 1 ) ] ; NEW_LINE for i in range ( 1 , 10 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT l = max ( 0 , j - k ) NEW_LINE r = min ( 9 , j + k ) NEW_LINE dp [ i ] [ l ] = dp [ i ] [ l ] + dp [ i - 1 ] [ j ] NEW_LINE dp [ i ] [ r + 1 ] = dp [ i ] [ r + 1 ] - dp [ i - 1 ] [ j ] NEW_LINE DEDENT for j in range ( 1 , 10 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j ] + dp [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT count = count + dp [ n ] [ i ] NEW_LINE DEDENT return count NEW_LINE DEDENT n , k = 2 , 1 NEW_LINE print ( getCount ( n , k ) ) NEW_LINE