Python 代码

L, R = map(int, input().split())

f = [[0] * 10 for _ in range(11)]

for i in range(10): f[1][i] = 1
for i in range(2, 11):
    for j in range(10):
        for k in range(10):
            if abs(j - k) >= 2:
                f[i][j] += f[i-1][k]
def dp(x):
    if x == 0: return 0
    nums = []
    while x:
        nums.append(x % 10)
        x //= 10
    pre = -1
    res = 0
    for i in range(len(nums)-1, -1, -1):
        num = nums[i]
        for j in range(num):
            if abs(j - pre) >= 2:
                res += f[i+1][j]
        if abs(pre - num) >= 2: pre = num 
        else: break
        if i == 0: res += 1

    for i in range(1, len(nums)):
        for j in range(1, 10):
            res += f[i][j]
    return res
print(dp(R) - dp(L-1))