数位DP入门：从Windy数问题详解记忆化搜索与状态设计

1. 从一道题看数位DP的核心思想

Windy数的定义是这样的：不含前导零且相邻两个数字之差至少为2的正整数。比如 135 是 Windy 数（1和3差2，3和5差2），而 123 不是（1和2差1）。题目通常要求统计区间 [A, B] 内 Windy 数的个数，A 和 B 的规模可以到 2×10^9 甚至更大。

第一次接触这道题的人，直觉反应往往是暴力枚举。但区间上界动辄十亿级别，逐个判断必然超时。这时候就需要引入数位DP——一种专门处理“统计满足某些数位约束条件的数字个数”的动态规划方法。

数位DP的核心思路可以用一句话概括：把数字按位拆开，从高位到低位逐位确定，用状态记录前缀信息，用记忆化搜索避免重复计算。它解决的不是某一道具体题，而是一整类问题——只要约束条件可以逐位传递，数位DP就能派上用场。

这篇文章我会从零把 Windy 数这道题拆透。不管你是刚学数位DP的新手，还是做过几道题但总觉得“知其然不知其所以然”的朋友，我都会把状态设计、边界处理、记忆化实现、以及那些容易踩的坑讲清楚。代码用 C++ 给出，但思路是语言无关的。

2. 数位DP的通用框架与Windy数的特殊性

2.1 数位DP到底在“DP”什么

很多人学数位DP的时候，第一反应是“这跟普通DP有什么关系”。其实数位DP的本质是按位决策的阶段化动态规划。

想象你在逐位填写一个数字。最高位可以填 0 到 9（但要注意前导零），次高位在前一位确定后也有若干选择，依此类推。每一位的选择构成了一个决策序列，而约束条件（比如相邻位之差至少为2）只依赖于相邻的决策。这种“决策只依赖有限前缀信息”的结构，天然适合DP。

状态通常设计成dp[pos][...]，其中pos表示当前处理到第几位，后面的维度记录前缀的关键信息。对于 Windy 数，关键信息就是上一位填了什么数字，因为约束是相邻两位的差。

2.2 为什么用记忆化搜索而不是递推

数位DP有两种主流写法：递推式和记忆化搜索式。我强烈建议新手从记忆化搜索入手，原因有三。

第一，记忆化搜索的代码结构和暴力DFS几乎一致，只是多了一个dp数组记录已计算的状态，思维负担小。第二，边界条件（比如是否顶到上界、是否有前导零）可以在递归参数里自然表达，不需要在递推中小心翼翼地分类讨论。第三，调试方便，出问题的时候打印递归树一目了然。

递推式写法的优势在于常数小、可以预处理，但在 Windy 数这种带前导零和上界约束的场景下，记忆化搜索的清晰度完胜。等你把记忆化搜索写熟了，再去研究递推式也不迟。

2.3 Windy数约束的数学本质

Windy数的约束“相邻两位之差至少为2”，翻译成数学语言就是：对于数字的相邻两位 $d_i$ 和 $d_{i+1}$，要求 $|d_i - d_{i+1}| \geq 2$。

这个约束有几个特点值得注意。它是局部约束——只涉及相邻两位，不涉及全局。它是对称的——差的正负不影响判断。它还是可增量验证的——填新的一位时，只需要知道上一位是什么，就能判断当前选择是否合法。

正因为约束是局部的、可增量验证的，我们才能把“上一位数字”作为DP状态的一部分。如果约束涉及所有位（比如“各位数字之和为某值”），状态设计就要换思路了——那类问题需要把“和”作为状态维度。

2.4 前导零：最容易被忽视的细节

Windy数定义里有一句“不含前导零”，这句话坑了无数人。

为什么前导零特殊？因为前导零不算数字的一部分。比如数字 5，按位拆开是005，但前导的两个零不应该参与“相邻位之差”的判断。如果代码里不处理前导零，就会把0和0的差（为0，小于2）当成非法，导致所有位数不足的数字全被判错。

处理方式是在递归参数里加一个lead（或叫started）标志，表示“当前是否还在处理前导零”。如果还在前导零阶段，当前位填0时下一位仍然处于前导零状态，且不触发相邻位约束；一旦填了非零数字，lead变为 false，后续位就要正常判断约束了。

这个细节我在第一次写的时候完全没意识到，样例过了但提交WA，debug了半天才发现问题。后面会详细讲怎么处理。

3. 状态设计与转移方程的完整推导

3.1 状态定义

我们定义记忆化搜索函数：

int dfs(int pos, int pre, bool limit, bool lead)

四个参数的含义分别是：

• pos：当前正在填第几位（从高位往低位，pos 从总位数减到0）
• pre：上一位填的数字（如果还在前导零阶段，pre 可以设为一个特殊值，比如 -1 或 11）
• limit：当前位是否受到上界约束（即前缀是否和上界的前缀完全相同）
• lead：当前是否仍处于前导零阶段

返回值是从当前状态出发，能填出多少个合法的 Windy 数。

dp数组记录的是无上界约束且非前导零阶段的状态，即dp[pos][pre]。为什么只记这两个维度？因为limit和lead是“路径相关”的临时状态，不同的路径可能到达同一个(pos, pre)但limit/lead不同，所以不能混在一起记忆化。标准做法是只在!limit && !lead时记录和查询dp。

3.2 转移过程

在dfs(pos, pre, limit, lead)中，我们枚举当前位能填的数字d：

• 如果limit为真，d的上界是当前位的上界数字up；否则d可以取到 9。
• 如果lead为真且d == 0，说明还在前导零阶段，下一位的pre仍然是特殊值，lead保持为真。
• 如果lead为真且d != 0，前导零阶段结束，lead变为假，但此时不需要检查相邻位约束（因为这是第一个有效数字）。
• 如果lead为假，则需要检查abs(d - pre) >= 2，不满足则跳过。

递归到dfs(pos-1, d, limit && (d == up), lead && (d == 0))，累加返回值。

递归终点是pos == 0，此时如果已经脱离前导零阶段（!lead），返回1（表示填出了一个合法数字）；如果还在前导零阶段（说明整个数字就是0），返回0（因为Windy数是正整数，0不算）。

3.3 为什么pre要设特殊值

当lead为真时，pre其实没有意义，因为还没有填过有效数字。但为了代码统一，我们给pre设一个不会和任何数字产生合法差的特殊值，比如 11（因为数字范围是0到9，11和任何数字的差都大于等于2）。

这样即使代码不小心在lead为真时检查了约束，也不会误判。当然，更稳妥的做法是在lead为真时直接跳过约束检查，用条件判断明确表达意图。

3.4 区间答案的转化

题目要求 [A, B] 内的 Windy 数个数。标准技巧是用前缀和思想：

answer = count(B) - count(A - 1)

其中count(n)统计 [1, n] 内的 Windy 数个数。这样我们只需要实现一个count函数，把上界设为 n，跑一次数位DP即可。

注意A - 1可能为0，而count(0)应该返回0（因为Windy数是正整数）。这个边界要处理好。

4. 代码实现与逐行解析

4.1 完整代码

#include <bits/stdc++.h> using namespace std; int dp[15][15]; // dp[pos][pre] int digit[15]; // 存储上界的各位数字 int dfs(int pos, int pre, bool limit, bool lead) { if (pos == 0) return lead ? 0 : 1; if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre]; int up = limit ? digit[pos] : 9; int res = 0; for (int d = 0; d <= up; d++) { if (lead) { if (d == 0) { res += dfs(pos - 1, 11, limit && (d == up), true); } else { res += dfs(pos - 1, d, limit && (d == up), false); } } else { if (abs(d - pre) >= 2) { res += dfs(pos - 1, d, limit && (d == up), false); } } } if (!limit && !lead) dp[pos][pre] = res; return res; } int count(int n) { if (n <= 0) return 0; int len = 0; while (n) { digit[++len] = n % 10; n /= 10; } memset(dp, -1, sizeof(dp)); return dfs(len, 11, true, true); } int main() { int A, B; cin >> A >> B; cout << count(B) - count(A - 1) << endl; return 0; }

4.2 关键行解析

dp数组大小设为[15][15]，第一维是位数（最多10位左右，15足够），第二维是上一位数字（0到9，加上特殊值11，所以15也够）。初始化为 -1 表示未计算。

digit数组存储上界的各位数字，注意是从低位到高位存储的，即digit[1]是个位，digit[len]是最高位。这样递归时pos从len递减到1，正好对应从高位到低位。

递归终点pos == 0时，如果lead为真说明整个数字都是0（前导零一直没结束），返回0；否则返回1。

记忆化的条件是!limit && !lead。这一点非常关键——只有不受上界约束且已经脱离前导零的状态才能被复用。因为受上界约束的状态依赖于具体的上界，不同上界下不能混用；前导零阶段的状态转移规则不同，也不能和正常状态混用。

枚举当前位时，up根据limit决定。limit && (d == up)表示下一位是否仍然受约束——只有当前位顶到上界且当前位等于上界数字时，下一位才继续受约束。

4.3 复杂度分析

状态数是pos乘以pre，大约是 10 × 12 = 120 个。每个状态枚举最多10个数字，转移代价 O(10)。所以单次count的时间复杂度是 O(位数 × 10 × 10)，也就是几百次操作，非常快。

空间上dp数组只有 15 × 15，可以忽略不计。这就是数位DP的威力——把指数级的枚举压缩到了多项式级别。

4.4 一个容易写错的地方

memset(dp, -1, sizeof(dp))这行必须放在count函数内部，每次调用count前重新初始化。因为count(B)和count(A-1)的上界不同，limit相关的状态不能复用，虽然我们只记忆化!limit的状态，理论上可以复用，但为了保险和代码清晰，每次重新初始化是最稳妥的做法。

如果你追求极致性能，可以只初始化一次，因为!limit && !lead的状态确实和上界无关。但实测下来，重新初始化的开销微乎其微，没必要为了这点性能牺牲代码的可读性和正确性。

5. 常见错误与调试技巧

5.1 前导零处理错误的典型症状

最常见的错误就是前导零没处理好。症状是：对于单位数（1到9），答案全部偏小。因为代码把前导零也当成了有效数字，0和第一个有效数字之间的差可能小于2，导致合法的单位数被误判。

比如数字 5，拆成005。如果不管前导零，会检查0和0的差（0 < 2，非法），直接判错。正确的做法是前导零阶段不检查约束。

调试方法：单独测试count(9)，正确答案是9（1到9都是Windy数，因为单个数字没有相邻位约束）。如果输出小于9，基本可以确定是前导零问题。

5.2 limit标志传递错误

另一个常见错误是limit的传递写错。正确的写法是limit && (d == up)，而不是简单的limit。如果写成limit，那么只要当前位受约束，下一位就永远受约束，导致枚举范围被错误地限制。

举个例子，上界是 25。第一位up = 2，如果填d = 1，那么下一位其实不受约束了（因为前缀 1 小于上界前缀 2），可以填 0 到 9。但如果错误地传递limit = true，下一位就只能填到 5，漏掉了很多合法数字。

5.3 dp数组维度不足

dp[pos][pre]中pre的范围是 0 到 9 加上特殊值 11，所以第二维至少要是 12。如果开成dp[15][10]，访问dp[pos][11]就会越界，可能读到垃圾值导致答案错误，也可能直接运行时错误。

建议第二维开到 15 或 20，留足余量。这种数组越界问题在本地可能不报错（因为栈上内存布局的巧合），但提交到评测机就挂了，非常难查。

5.4 常见问题速查表

5.5 对拍验证

写完代码后，强烈建议写一个暴力版本对拍。暴力版本直接枚举 1 到 n，逐个判断是否是 Windy 数。对于小范围（比如 n 到 10000），对拍能快速发现逻辑错误。

对拍代码大概长这样：

bool isWindy(int x) { if (x < 10) return true; int pre = x % 10; x /= 10; while (x) { int cur = x % 10; if (abs(cur - pre) < 2) return false; pre = cur; x /= 10; } return true; } int brute(int n) { int cnt = 0; for (int i = 1; i <= n; i++) if (isWindy(i)) cnt++; return cnt; }

随机生成若干组 A、B，比较两个版本的输出。如果全部一致，基本可以放心提交。

6. 数位DP的扩展与实战心得

6.1 从Windy数到其他数位DP问题

Windy数是最基础的一类数位DP——约束只涉及相邻位。掌握了它之后，很多变种问题都能触类旁通。

比如“不要62”问题（数字中不能出现连续的62，也不能出现4），约束是“当前位不能是4”和“当前位是2时上一位不能是6”。状态设计类似，只是判断条件变了。

再比如“各位数字之和为某值”的问题，状态需要增加一维记录当前的和。这时候dp[pos][sum][pre]可能维度就上去了，需要根据题目规模判断是否可行。

还有“数字中某类数字出现次数”的问题，状态里要记录出现次数。这类问题的共同点是：约束可以逐位增量验证，所以适合数位DP。

6.2 记忆化搜索的通用模板

把Windy数的代码抽象一下，可以得到数位DP记忆化搜索的通用模板：

int dfs(int pos, /* 前缀状态 */, bool limit, bool lead) { if (pos == 0) return /* 终止条件 */; if (!limit && !lead && dp[pos][...] != -1) return dp[pos][...]; int up = limit ? digit[pos] : 9; int res = 0; for (int d = 0; d <= up; d++) { if (/* 前导零处理 */) { // 继续前导零或开始有效数字 } else { if (/* 约束条件 */) { res += dfs(pos - 1, /* 新状态 */, limit && (d == up), false); } } } if (!limit && !lead) dp[pos][...] = res; return res; }

这个模板适用于绝大多数数位DP问题。你只需要根据具体题目替换“前缀状态”、“终止条件”和“约束条件”即可。

6.3 我踩过的坑与经验总结

第一个坑是前导零和数字0的区分。Windy数定义是正整数，所以0不算。但有些题目可能把0算进去，或者把前导零的处理方式不同。每次做题都要仔细读题，确认0的处理方式。

第二个坑是dp数组的初始化位置。我见过有人在全局初始化一次，然后多次调用count不重新初始化，结果第二次调用的答案受第一次影响。虽然理论上!limit && !lead的状态可以复用，但前提是你的状态设计确实和上界无关。为了保险，每次重新初始化。

第三个坑是limit和lead同时为真的情况。这种情况下状态不能被记忆化，因为不同的上界会导致不同的转移。代码里if (!limit && !lead)这个条件必须写对，不能漏掉任何一个。

第四个坑是递归深度。虽然数位DP的位数通常只有10到20位，递归深度很浅，但如果题目给的数字范围特别大（比如10^18），位数可能到19位，递归深度19层，完全没问题。但如果用递推式写法，要注意数组大小。

6.4 性能优化的小技巧

虽然数位DP本身已经很快了，但在某些极端情况下（比如多组测试数据），还是可以优化一下。

第一个技巧是预处理dp数组。如果多组数据的上界位数相同，可以只初始化一次dp数组，然后复用。但要注意limit和lead的处理。

第二个技巧是把pre的维度压缩。如果约束只关心“上一位是否大于等于2”之类的布尔信息，可以把pre压缩成几个状态，减少状态数。

第三个技巧是用递推代替记忆化搜索。递推式写法常数更小，但代码更复杂。对于Windy数这种简单问题，记忆化搜索已经足够快，没必要上递推。

6.5 数位DP的思维训练建议

如果你想彻底掌握数位DP，我的建议是按以下顺序刷题：

先做Windy数，理解基本框架和前导零处理。然后做“不要62”，理解多条件约束。接着做“数字计数”（统计每个数字出现次数），理解多状态维度。最后做“各位数字之和”类问题，理解状态维度的扩展。

每道题做完后，不要急着下一道，而是回头想想：这道题的状态设计为什么是这样的？约束条件是怎么体现在转移里的？边界条件是怎么处理的？把这些问题想清楚，比刷十道题都有用。

数位DP的难点从来不是代码，而是状态设计和边界处理。代码模板是固定的，但每道题的状态和边界都不一样。多思考、多总结，才能真正做到举一反三。

我在实际做题的时候发现，很多数位DP的WA都不是算法错误，而是边界没处理好。前导零、数字0、上界为0、区间左端点为1……这些边界情况一个个测过去，基本就能定位问题。所以我的习惯是写完代码后，先用手动构造的小数据测边界，再用对拍验证一般情况，最后才提交。这个习惯帮我省了很多次罚时。