好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

原题来自：SCOI 2009

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。

Windy 想知道，在 $A$ 和 $B$ 之间，包括 $A$ 和 $B$，总共有多少个 Windy 数？

输入格式

一行两个整数，分别为 $A, B$。

输出格式

输出一个整数，表示答案。

样例

样例输入 1

1 10

样例输出 1

9

样例解释 1

$A=1, B=10$，Windy 数要求相邻数字之差至少为 2，且不含前导零。

在 $1$ 到 $10$ 之间的 Windy 数有：$1,2,3,4,5,6,7,8,9$（所有一位数都满足，因为没有相邻数字）。
注意 $10$ 不满足，因为 $1$ 和 $0$ 的差为 $1<2$。

所以共 $9$ 个。

样例输入 2

25 50

样例输出 2

20

数据范围

• 对于 $20\%$ 的数据，满足 $1 \le A \le B \le 10^6$；
• 对于 $100\%$ 的数据，满足 $1 \le A \le B \le 2\times 10^9$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

提示
此题为 数位 DP 问题。

状态设计：$dp[pos][last][lead]$ 表示处理到第 $pos$ 位，上一位数字是 $last$（若前面全是前导零则 $last$ 为 $-1$ 或特殊值），$lead$ 表示是否前面全是前导零。

转移条件：

• 如果 $lead$ 为真，当前位可以从 $0$ 到 $9$，但若当前位选 $0$，则 $lead$ 仍为真，$last$ 不变（仍为 $-1$）；
• 如果 $lead$ 为假，当前位必须满足与 $last$ 的差的绝对值 $\ge 2$。

最终要求不含前导零，所以只有 $lead$ 为假的状态才算有效数。

记忆化：$dp[pos][last][lead]$，其中 $last$ 范围 $0\sim 9$ 或 $-1$（可以用 $10$ 表示 $-1$ 特殊状态）。

具体步骤：

1. 将数字拆分成数位数组；
2. DFS(pos, last, lead, limit)：
   • pos：当前处理到的位（从高位到低位）；
   • last：上一位数字（若前面全为前导零，last=10 表示未开始）；
   • lead：是否前面全是 0；
   • limit：是否受到上限限制。
3. 当 pos 到达末尾时，如果 lead 为真，则返回 0（表示数字为 0，但 Windy 数是正整数，所以排除），否则返回 1。
4. 转移：枚举当前位数字 d 从 0 到 (limit ? digit[pos] : 9)，若 lead 为真且 d==0，则继续 lead 为真且 last 不变；否则若 lead 为真且 d>0，则 lead 变为假，且 last 更新为 d；若 lead 为假，则需满足 |d-last|>=2。

最终答案为：dfs(0, 10, true, true)（假设 last=10 表示前面全 0）。

答案 = calc(B) - calc(A-1)。

复杂度：状态数 $O(\text{位数} \times 11 \times 2)$，可以快速计算。

注意：当数字为 0 时，DFS 返回 0，因为 Windy 数必须是正整数。