详解'Count of N-digit numbers with absolute difference of adjacent digits not exceeding K'的逻辑

Question

谁能帮我理解以下动态编程问题的逻辑在 geeksforgeeks.com 找到这个问题。我看完了提供的答案还是无法理解。

问题：

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解法：

# 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))

此代码由 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/

我无法理解以下几行的逻辑

# 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 1

N=2 所以我们处理的是严格的 2 位数字

K=1 因此当前号码中的每个数字不得比其邻居大或小 1 位

虽然答案是26（这样的数字的个数），但让我们看看为什么答案包括10、11和12但是不是 13

10 很好，因为 1 - 0（10 的位数）的绝对值小于或等于 1（ K)

的值

13 不好，因为 1 - 3 的绝对值是 2 并且 2 大于 K

请注意，随着 N 的增加，所需的成对数字比较次数也会增加。

我将跳过使用无意义的变量名解析其他人的代码。以下是我可能会尝试解决的方法：

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))

详解'Count of N-digit numbers with absolute difference of adjacent digits not exceeding K'的逻辑

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

python

algorithm

dynamic-programming

multidimensional-array

python-3.x