- 不得不说，数位DP是我掌握的最不好的一个板块。其实数位DP还挺好理解的，状态设计也一目了然，但是请小心前导零。
- 从数位DP最基础的模版题：windy数开始做起
P2657 [SCOI2009] windy 数
- 题意：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？\(1≤a≤b≤2×10^9\)
状态分析
- 首先,这巨大的数据范围让我们不可能正常DP。事实上，数位DP的最明显特征就是数据范围，这就是让你明摆着写数位DP
- 那么知道是数位DP了，考虑状态。数位DP的状态是雷同的。主要由位数、推出下一位必须的条件以及是否压位、是否有前导零等东西构成。（压位的概念后面讲）
但状态并不是一成不变的。虽然大部分数位DP题已经相当类似，但也要“带着脑子做题” - 对于这道题而言，位数为9，因为我们只需要枚举每一位的数字大小就行了，我们并不关心整个数字是多少。
- 推出下一位必须的条件很显然只有上一位数的大小，只要相减绝对值小于2，因此记下来
- 是否压位以及是否有前导零在此题显然需要考虑。因为前导零根据题意并不算做真正的“数字”，并不需要满足“相邻数字差至少为2”的条件，因此会影响答案。
- “压位”的意思是指是否这一位前枚举的数与我们的“上界”（就是输入进来的数）完全相同。
比如我们已经枚举了113***（后面的*是还没枚举的），输入进来的数是113333，那我们第四位就不能是4及以上的数。
因此我们需要记录是否有这种特殊的情况。但我们最好不要把它写进DP状态里，因为有的题会有多组数据。
如果我们希望这种特殊的情况不影响下一组数据，我们必须每次都清空DP数组，而这会极大地增大常数，对于一些卡常题极不友好，因此养成好习惯，从模板题做起，不要把“压位”写进状态里。 - 综上，我们设定的DP状态是 \(f_{i,j}\) 表示枚举到倒数第 \(i\) 位（倒着枚举好统计答案），上一位是 \(j\) 的情况总数
- 至于压位与前导零，在哪里，之后讲。
粗略写法
- 众所周知，DP有两种写法：记忆化搜索以及正着写循环。
一般而言，数位DP使用记忆化搜索。记搜有两个优点：
- 可以合理方便地记下上文所说的压位以及前导零等不计入状态的信息
- 代码直观合理，短小精悍。写循环的话有的时候循环特别多（可以去找一些数位DP题的循环写法，十分壮观）
- 最后是几个实现的小细节：
- 根据题干，枚举的数与上一位之间的差的绝对值至少为2，但如果上一位是前导零的话那么就没有这个限制
- 最后的边界条件需要注意。由于我使用vector来存储上界（原数），因此边界是
len==-1 - 注意要没有压位并且没有前导零才能记忆化，因为状态中没有这两个影响最终答案的值
- 注意判断压位后确定上界
- 我们将原先的 \(a \to b\) 的区间拆分成 \(1 \to a-1\) 与 \(1 \to b\) 两个区间求值后做差
- 有了状态与记忆化搜索的写法，我们就可以大概码出代码了。
code
（略有压行）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e9+7;
int f[20][20];
vector <int> shu;
void init(){memset(f,-1,sizeof(f));}
int dfs(int len,int last,bool qian,bool ya)
{
if(len==-1) return 1ll;//边界条件
if(!ya&&!qian&&f[len][last]!=-1) return f[len][last];//注意不压位无前导零才能记忆化
int up=ya?shu[len]:9,res=0;//注意压位的上界
for(int i=0;i<=up;i++){
if(abs(last-i)>=2||qian)//如果是有前导零就可以无视条件
res+=dfs(len-1,i,qian&&(!i),ya&&(i==up));
//状态简洁一点，不要像某些 题解一样写的一大堆，其实一行就行了
}
if(!ya&&!qian) f[len][last]=res;return res;
}
int work(int x)
{
shu.clear();//记得清空
while(x){shu.push_back(x%10),x/=10;}//用vector存上界
return dfs(shu.size()-1,-2,1,1);//从高向低位枚举
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//关流，好习惯，但只能用cin
int l,r;cin>>l>>r;init();
cout<<work(r)-work(l-1)<<'\n';//做差
return 0;
}
时、空复杂度
- 时间复杂度一般而言就是你开的数组大小。因为一般而言你会将整个数组都跑一遍，又因为记忆化，所以就是数据大小
- 为什么要强调空间复杂度呢？因为有一些毒瘤卡常题，因此注意状态设计，需要离散化的离散化，需要再压缩的再压缩