【数位DP】蓝桥云课 - 小蓝的生日礼物（Windy数） 题解

【数位DP】蓝桥云课 - 小蓝的生日礼物 题解1. 题目概述题目名称小蓝的生日礼物题目大意在区间[ a , b ] [a, b][a,b]中挑选满足“相邻两位的数字之差至少为 2”的整数求满足条件的数字个数。数据规模1 ≤ a ≤ b ≤ 10 9 1 \le a \le b \le 10^91≤a≤b≤1092. 解题思路本题是典型的**数位 DP数位动态规划**问题要求统计区间[ a , b ] [a, b][a,b]内满足特定数位限制的数字数量。区间转换通过前缀和思想求区间[ a , b ] [a, b][a,b]内满足条件的个数可以转化为求解solve(b) - solve(a - 1)其中solve(x)表示求[ 0 , x ] [0, x][0,x]范围内符合条件的数字个数。DFS 状态设计通过记忆化搜索来实现数位 DPpos当前处理到的数位从高位向低位。pre前一位填入的数字用于判断相邻差值是否≥ 2 \ge 2≥2。lead前导零标记。如果为true说明前面全为 0当前位填 0 仍属于前导零不触发相邻差值的限制。limit最高位限制标记。如果为true当前位最大只能填到原数在该位的数字若为false则可填0~9。状态转移与记忆化当pos -1时说明成功构造了一个合法数字返回1。当!limit !lead时说明当前状态不受上限限制且已离开前导零阶段结果具有通用性可以保存在dp[pos][pre]中后续重复遇到可直接返回。3. C 源码#includebits/stdc.husingnamespacestd;longlongdp[15][15];vectorintnum;/** * brief 数位 DP 记忆化搜索 * param pos 当前处理的数位索引从高到低 * param pre 前一位填入的数字 * param lead 是否包含前导零 * param limit 是否受到最高位限制 */intdfs(intpos,intpre,boollead,boollimit){if(pos-1)return1;// 递归基构造完成一个数// 记忆化检索if(!lead!limitdp[pos][pre]!-1){returndp[pos][pre];}longlongres0;intuplimit?num[pos]:9;// 当前可填的最大数字for(intd0;dup;d){if(lead){if(d0){// 仍处于前导零状态resdfs(pos-1,0,true,limit(dup));}else{// 离开前导零状态resdfs(pos-1,d,false,limit(dup));}}else{// 正常填数需满足相邻差值 2if(abs(d-pre)2){resdfs(pos-1,d,false,limit(dup));}}}// 状态记录if(!limit!lead){dp[pos][pre]res;}returnres;}/** * brief 计算 [0, x] 范围内满足条件的数字个数 */longlongsolve(longlongx){if(x0)return0;num.clear();while(x){num.push_back(x%10);x/10;}if(num.empty())num.push_back(0);returndfs(num.size()-1,0,true,true);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);memset(dp,-1,sizeof(dp));longlongA,B;if(cinAB){coutsolve(B)-solve(A-1)\n;}return0;}4. 复杂度分析时间复杂度最大位数L ≈ 10 L \approx 10L≈10对于10 9 10^9109级别的数。状态数为位数 × 前一位数字 10 × 10 100 \text{位数} \times \text{前一位数字} 10 \times 10 100位数×前一位数字10×10100种每个状态遍历0 ∼ 9 0 \sim 90∼9转移运行时间不超过 1ms完全满足时间限制。空间复杂度O ( L × 10 ) O(L \times 10)O(L×10)使用极少的额外内存数位 DP 数组仅需15 × 15 15 \times 1515×15。