1. 问题描述：
Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？
输入格式
共一行，包含两个整数 A 和 B。
输出格式
输出一个整数，表示答案。
数据范围
1 ≤ A ≤ B ≤ 2 × 10 ^ 9
输入样例1：
1 10
输出样例1：
9
输入样例2：
25 50
输出样例2：
20
来源：https://www.acwing.com/problem/content/1085/
2. 思路分析：
分析题目可以知道我们需要求解区间[a，b]满足不包含前导0并且相邻两个数字的差为2性质的数的个数，由这个特点可以知道这道题目属于数位dp的题目。对于数位dp的题目都是类似的套路，借助于树的形式来分析，具体的实现步骤如下：以区间的其中一个端点y为例，首先是需要预处理二维数组f，这样后面在枚举y的每一位的时候左边的分支可以直接计算出来（一般都是组合数），类似于1082 题数字游戏，当前的最高位只与次高位是有关系的，所以我们可以借助于1082题f数组的状态表示和状态计算的思路，定义一个二维数组f，其中f[i][j]表示最高位为j且总共为i位的Windy数的个数，怎么样递推呢？（状态计算），我们可以使用三层循环枚举，第一层循环枚举当前总共有i位，第二层循环枚举i位数字的最高位填j，第三层循环枚举次高位填k，只有当abs(j - k) >= 2说明才是合法的，这样我们通过预处理就将所有总共有i位最高位填k的情况计算出来了，预处理的目的是为了枚举左边分支填0~x-1的时候可以直接计算出对应的结果；预处理f数组之后，我们需要将区间端点y的每一位扣出来存储到nums中，然后逆序枚举nums中的每一位数字，对于当前的第i位数字x = nums[i]，我们可以尝试填0~x-1，当第i位填0~x-1的时候就可以直接累加上之前预处理的结果了，进入到循环的下一位的时候表示第i位填x，当我们在枚举的时候发现不满足条件之后可以直接break。这道题目的处理方式与1082题很像的可以对比着理解。
3. 代码如下：
from typing import List
class Solution:
# 与1082不降数的题目是类似的都是枚举最高位与次高位填的数字是什么
def init(self, N: int, f: List[List[int]]):
# 注意这里在枚举的时候需要计算到dp[i][0]的值, 如果不算会出现错误, 因为例如2位数字n = 20可以由dp[1][0]转移过来
for i in range(10): f[1][i] = 1
for i in range(2, N):
for j in range(10):
for k in range(10):
if abs(j - k) >= 2:
f[i][j] += f[i - 1][k]
# 计算区间[0, n]的Windy数的个数, 这里将0算不算答案都没有影响, 因为做差之后结果都等于0
def dp(self, n: int, f: List[List[int]]):
# 边界, 这里将0归为不是windy数
if n == 0: return 0
nums = list()
while n > 0:
nums.append(n % 10)
n //= 10
# last表示上一个填的数字只要与0~9的数字绝对值差值大于2即可
res, last = 0, -2
for i in range(len(nums) - 1, -1, -1):
x = nums[i]
# 判断是否是首位, 首位应该从1开始填, 否则可以填0, 枚举当前这一位填小于x的情况
for j in range(1 if i == len(nums) - 1 else 0, x):
if abs(j - last) >= 2:
res += f[i + 1][j]
if abs(last - x) >= 2:
# 当满足条件之后说明可以接着尝试填下一个数字
last = x
# 当前的x与上一位填的数字last不满足题目的要求, 说明这一位填x后面不管填什么的方案都是不满足题目要求了直接break
else:
break
# 最右边那个分支
if i == 0: res += 1
# 枚举之前没有计算的前导0的特殊情况, 只需要枚举到len(nums) - 1即可, 最高位上面已经累加到答案中了
for i in range(1, len(nums)):
# 当前有1~9位最高位为1~9的方案数目
for j in range(1, 10):
res += f[i][j]
return res
def process(self):
x, y = map(int, input().split())
N = 11
f = [[0] * 10 for i in range(N)]
self.init(N, f)
return self.dp(y, f) - self.dp(x - 1, f)
if __name__ == "__main__":
print(Solution().process())