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

1. 从一道题看数位DP的核心思想Windy数的定义是这样的不含前导零且相邻两个数字之差至少为2的正整数。比如 135 是 Windy 数1和3差23和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_{i1}$要求 $|d_i - d_{i1}| \geq 2$。这个约束有几个特点值得注意。它是局部约束——只涉及相邻两位不涉及全局。它是对称的——差的正负不影响判断。它还是可增量验证的——填新的一位时只需要知道上一位是什么就能判断当前选择是否合法。正因为约束是局部的、可增量验证的我们才能把“上一位数字”作为DP状态的一部分。如果约束涉及所有位比如“各位数字之和为某值”状态设计就要换思路了——那类问题需要把“和”作为状态维度。2.4 前导零最容易被忽视的细节Windy数定义里有一句“不含前导零”这句话坑了无数人。为什么前导零特殊因为前导零不算数字的一部分。比如数字 5按位拆开是005但前导的两个零不应该参与“相邻位之差”的判断。如果代码里不处理前导零就会把0和0的差为0小于2当成非法导致所有位数不足的数字全被判错。处理方式是在递归参数里加一个lead或叫started标志表示“当前是否还在处理前导零”。如果还在前导零阶段当前位填0时下一位仍然处于前导零状态且不触发相邻位约束一旦填了非零数字lead变为 false后续位就要正常判断约束了。这个细节我在第一次写的时候完全没意识到样例过了但提交WAdebug了半天才发现问题。后面会详细讲怎么处理。3. 状态设计与转移方程的完整推导3.1 状态定义我们定义记忆化搜索函数int dfs(int pos, int pre, bool limit, bool lead)四个参数的含义分别是pos当前正在填第几位从高位往低位pos 从总位数减到0pre上一位填的数字如果还在前导零阶段pre 可以设为一个特殊值比如 -1 或 11limit当前位是否受到上界约束即前缀是否和上界的前缀完全相同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到911和任何数字的差都大于等于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)正确答案是91到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 常见问题速查表症状可能原因排查方法单位数答案偏小前导零未处理测试 count(9) 是否为9大区间答案偏小limit传递错误检查是否写成 limit (d up)随机错误或崩溃dp数组越界检查 pre 维度是否够大答案偏大递归终点返回条件错误检查 pos0 时 lead 的判断多次调用结果不一致dp未重新初始化确认每次 count 前 memset5.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……这些边界情况一个个测过去基本就能定位问题。所以我的习惯是写完代码后先用手动构造的小数据测边界再用对拍验证一般情况最后才提交。这个习惯帮我省了很多次罚时。