【数位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≤109

---

2. 解题思路

本题是典型的**数位 DP（数位动态规划）**问题，要求统计区间[ a , b ] [a, b][a,b]内满足特定数位限制的数字数量。

1. 区间转换：
   通过前缀和思想，求区间[ a , b ] [a, b][a,b]内满足条件的个数，可以转化为求解solve(b) - solve(a - 1)，其中solve(x)表示求[ 0 , x ] [0, x][0,x]范围内符合条件的数字个数。

2. DFS 状态设计：
   通过记忆化搜索来实现数位 DP：

   • pos：当前处理到的数位（从高位向低位）。
   • pre：前一位填入的数字（用于判断相邻差值是否≥ 2 \ge 2≥2）。
   • lead：前导零标记。如果为true，说明前面全为 0，当前位填 0 仍属于前导零，不触发相邻差值的限制。
   • limit：最高位限制标记。如果为true，当前位最大只能填到原数在该位的数字；若为false，则可填0~9。

3. 状态转移与记忆化：

   • 当pos == -1时，说明成功构造了一个合法数字，返回1。
   • 当!limit && !lead时，说明当前状态不受上限限制且已离开前导零阶段，结果具有通用性，可以保存在dp[pos][pre]中，后续重复遇到可直接返回。

---

3. C++ 源码

#include<bits/stdc++.h>usingnamespacestd;longlongdp[15][15];vector<int>num;/** * @brief 数位 DP 记忆化搜索 * @param pos 当前处理的数位索引（从高到低） * @param pre 前一位填入的数字 * @param lead 是否包含前导零 * @param limit 是否受到最高位限制 */intdfs(intpos,intpre,boollead,boollimit){if(pos==-1)return1;// 递归基：构造完成一个数// 记忆化检索if(!lead&&!limit&&dp[pos][pre]!=-1){returndp[pos][pre];}longlongres=0;intup=limit?num[pos]:9;// 当前可填的最大数字for(intd=0;d<=up;d++){if(lead){if(d==0){// 仍处于前导零状态res+=dfs(pos-1,0,true,limit&&(d==up));}else{// 离开前导零状态res+=dfs(pos-1,d,false,limit&&(d==up));}}else{// 正常填数，需满足相邻差值 >= 2if(abs(d-pre)>=2){res+=dfs(pos-1,d,false,limit&&(d==up));}}}// 状态记录if(!limit&&!lead){dp[pos][pre]=res;}returnres;}/** * @brief 计算 [0, x] 范围内满足条件的数字个数 */longlongsolve(longlongx){if(x<0)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(cin>>A>>B){cout<<solve(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×10=100种，每个状态遍历0 ∼ 9 0 \sim 90∼9转移，运行时间不超过 1ms，完全满足时间限制。
• 空间复杂度：O ( L × 10 ) O(L \times 10)O(L×10)，使用极少的额外内存（数位 DP 数组仅需15 × 15 15 \times 1515×15）。