Explain the logic of ‘Count of N-digit numbers with absolute difference of adjacent digits not exceeding K’ in Detail

Can someone please help me understand the logic of following Dynamic Programmming question Found this one at geeksforgeeks.com. I am unable to understand even after going through the answer provided.

Question:

Count of N-digit numbers with absolute difference of adjacent digits not exceeding K | Set 2

Given two integers N and K, the task is to find the count of N-digit numbers such that the absolute difference of adjacent digits in the number is not greater than K.

Examples:

Input: N = 2, K = 1

Output: 26

Explanation: The numbers are 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99

Input: N = 3, K = 2

Output: 188

Python3 solution:

# Function to return the count of such numbers 
def getCount(n, K): 
    # For 1-digit numbers, the count is 10 irrespective of K 
    if(n == 1): 
        return 10

    # dp[j] stores the number of such i-digit numbers ending with j 
    dp = [0] * 11

    # Stores the results of length i 
    next = [0] * 11

    # Initialize count for 1-digit numbers 
    for i in range(1, 9 + 1): 
        dp[i] = 1

    # Compute values for count of digits greater than 1 
    for i in range(2, n + 1): 
        for j in range(9 + 1): 
            # Find the range of allowed numbers if last digit is j 
            l = max(0, j - k) 
            r = min(9, j + k) 

            # Perform Range update 
            next[l] += dp[j] 
            next[r + 1] -= dp[j] 

        # Prefix sum to find actual count of i-digit numbers ending with j 
        for j in range(1, 9 + 1): 
            next[j] += next[j - 1] 

        # Update dp[] 
        for j in range(10): 
            dp[j] = next[j] 
            next[j] = 0

    # Stores the final answer 
    count = 0
    for i in range(9 + 1): 
        count += dp[i] 

    return count 


if __name__ == '__main__': 
    n = 2
    k = 1
    print(getCount(n, k)) 

This code is contributed by Shivam Singh

Link: https://www.google.com/amp/s/www.geeksforgeeks.org/count-of-n-digit-numbers-with-absolute-difference-of-adjacent-digits-not-exceeding-k-set-2/amp/

I am unable to understand the logic in following lines

# Compute values for count of 

# digits greater than 1 

for i in range(2, n + 1): 

    for j in range(9 + 1): 



        # Find the range of allowed 

        # numbers if last digit is j 

        l = max(0, j - k) 

        r = min(9, j + k) 



        # Perform Range update 

        next[l] += dp[j] 

        next[r + 1] -= dp[j] 



    # Prefix sum to find actual count 

    # of i-digit numbers ending with j 

    for j in range(1, 9 + 1): 

        next[j] += next[j - 1] 



    # Update dp[] 

    for j in range(10): 

        dp[j] = next[j] 

        next[j] = 0

Answer

N=2 so we are dealing with strictly 2 digit numbers

K=1 so each digit in the current number shall be no more than 1 digit greater or less than its neighbors

While the answer is 26 (the count of such numbers), lets take a look at why the answer includes 10, 11, and 12 but not 13

10 is good as the absolute value of 1 – 0 (the digits of 10) is less than or equal to 1 (the value of K)

13 is bad as the absolute value of 1 – 3 is 2 and 2 is greater than K

Note that as N increases, the number of pairwise digit comparisons required will also increase.

I’ll skip parsing someone else’s code with meaningless variable names. Here is how I might attempt to solve this:

def is_valid_number(number_to_test, allowed_digit_spread):
    if number_to_test < 10:
        # apparently all 1 digit numbers pass
        return True

    # get the individual digits as a list
    digits = [int(digit) for digit in str(number_to_test)]

    for i in range(1, len(digits)):
        current_digit = digits[i]
        prior_digit = digits[i-1]
        if abs(current_digit - prior_digit) > allowed_digit_spread:
            # bad pairwise compare so reject
            return False

    return True

def get_numbers_to_test(allowed_digits):
    start = pow(10, allowed_digits -1)
    end = pow(10, allowed_digits)
    return range(start, end)

def getCount(allowed_digits, allowed_digit_spread):
    count = 0
    for n in get_numbers_to_test(allowed_digits):
        if is_valid_number(n, allowed_digit_spread):
            count += 1
    return count

if __name__ == '__main__':
    n = 2
    k = 1
    print(getCount(n, k))