【序】
数位dp就是套模板 ——lwz dalao
（数位dp确实可以套模板，但笔者建议还是要理解这个过程，这样才能灵活变化）
【引言】
数位dp一直以来是dp家族里比较冷门的一种，但一旦考察不会数位dp靠暴力很难骗分
今天我们就来分析一下数位dp的全过程
【引入】
首先我们要清楚数位dp解决的是什么问题：
求出在给定区间 [A,B] 内，符合条件 f(i) 的数 i 的个数。条件 f(i) 一般与数的大小无关，而与数的组成有关
由于数是按位dp，数的大小对复杂度的影响很小
【设计搜索】
这里我们使用记忆化搜索实现数位dp。本质上记搜其实就是dp，下文会重点介绍dp值的使用和记录
一、记搜过程
从起点向下搜索，到最底层得到方案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。
对于 [l,r] 区间问题，我们一般把他转化为两次数位dp,即找 [0,r] 和 [0,l-1] 两段，再将结果相减就得到了我们需要的 [l,r]
首先是数位dp基本的量数字位数 pos ，记录答案的 st ，最高位限制 limit （这个后面会讲）
我们还需要一个判断判断前导0的标记 lead （这个后面也会讲）
由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定），所以一般在dfs()中也要记录前一位或前几位数 pre 方便比较。
除此之外还可以传进更多参量以区分状态，视题意而定。
数位dp的状态能记录的最好都记录上 ——lwz dalao
【细节分析】
一、前导0标记lead
由于我们要搜的数可能很长，所以我们的直接最高位搜起
举个例子：假如我们要从 [0,1000] 找任意相邻两数相等的数
显然 111,222,888 等等是符合题意的数
但是我们发现右端点 1000 是四位数
因此我们搜索的起点是 0000 ，而三位数的记录都是 0111,0222,0888 等等
而这种情况下如果我们直接找相邻位相等则 0000 符合题意而 0111,0222,0888 都不符合题意了
所以我们要加一个前导0标记
-
如果当前位 lead=1 而且当前位也是0，那么当前位也是前导0， pos 1 继续搜；
-
如果当前位 lead=1 但当前位不是0，则本位作为当前数的最高位， pos 1 继续搜；（注意这次根据题意st或其他参数可能发生变化）
当然前导 0 有时候是不需要判断的，上述的例子是一个有关数字结构上的性质，0会影响数字的结构，所以必须判断前导0；而如果我们研究的是数字的组成（例如这个数字有多少个 1 之类的问题），0并不影响我们的判断，这样就不需要前导0标记了。总之，这个因题而异，并不是必须要标记（当然记了肯定是不会出错的）
二、最高位标记limit
我们知道在搜索的数位搜索范围可能发生变化；
举个例子：我们在搜索 [0,555] 的数时，显然最高位搜索范围是 0 ~ 5 ，而后面的位数的取值范围会根据上一位发生变化：
-
当最高位是 1 ~ 4 时，第二位取值为 [0,9] ;
-
当最高位是 5 时，第二位取值为 [0,5] （再往上取就超出右端点范围了）
为了分清这两种情况，我们引入了 \text{limit} 标记：
-
若当前位 limit=1 而且已经取到了能取到的最高位时，下一位 limit=1 ；
-
若当前位 limit=1 但是没有取到能取到的最高位时，下一位 limit=0 ；
-
若当前位 limit=0 时，下一位 limit=0 。
我们设这一位的标记为 limit ，这一位能取到的最大值为 res ，则下一位的标记就是 i==res && limit （ i 枚举这一位填的数）
三、dp值的记录和使用
最后我们考虑dp数组下标记录的值
本文介绍数位dp是在记忆化搜索的框架下进行的，每当找到一种情况我们就可以这种情况记录下来，等到搜到后面遇到相同的情况时直接使用当前记录的值。
dp数组的下标表示的是一种状态，只要当前的状态和之前搜过的某个状态完全一样，我们就可以直接返回原来已经记录下来的dp值。
再举个例子
假如我们找 [0,123456] 中符合某些条件的数
假如当我们搜到 1000jQuery33108684357930728313_1541404441669 时，dfs从下返上来的数值就是当前位是第 5 位，前一位是 0 时的方案种数，搜完这位会向上反，这是我们可以记录一下：当前位第 5 位，前一位是 0 时，有这么多种方案种数
当我们继续搜到 1010?? 时，我们发现当前状态又是搜到了第 5 位，并且上一位也是 0 ，这与我们之前记录的情况相同，这样我们就可以不继续向下搜，直接把上次的dp值返回就行了。
注意，我们返回的dp值必须和当前处于完全一样的状态，这就是为什么dp数组下标要记录 pos,pre 等参量了。
最重要的来了——
接着上面的例子，范围 [0,123456]
如果我们搜到了 1234?? ，我们能不能直接返回之前记录的：当前第 5 位，前一位是 4 时的dp值？
答案是否定的
我们发现，这个状态的dp值被记录时，当前位也就是第 5 位的取值是 [0,9] ，而这次当前位的取值是 [0,5] ，方案数一定比之前记录的dp值要小。
当前位的取值范围为什么会和原来不一样呢？
如果你联想到了之前所讲的知识，你会发现：现在的 limit=1 ，最高位有取值的限制。
因此我们可以得到一个结论：当 limit=1 时，不能记录和取用dp值！
类似上述的分析过程，我们也可以得出：当 lead=1 时，也不能记录和取用dp值！
p.s.当然没有这么绝对的说……因题而异的说……
以上就是计划搜索的完整步骤。
附图：
【模板】
【例题详解】
注： 推荐此题的原因是这道题涉及到的需要记录的量较多，比较典型，如果觉得比较难理解也没关系，先看下面的例题推荐
【题意简述】
定义一个正整数的价值是把这个数的十进制写出来之后，最长的等差子串的长度。
求 [l,r] 范围内数字价值的总和。
【分析】
这道题很显然是一道数位dp，那么我们应该怎么样设计状态和转移呢？
数位位置，前一位数，等差数列共差是一定要记录的
我们还要把当前最大价值和整个数最大值也作为状态
dp过程见代码注释（数位dp主要还是套板子呀）
【题目推荐】
-
[HDU2089]不要62
入门题，如果上面的例题没看懂可以先尝试一下这道题，如果上面的例题理解了这题可以秒切
-
P2657 [SCOI2009]windy数
-
P2602 [ZJOI2010]数字计数
这两题是数位dp题目里的基础题，多体会上述的讲解就能够顺利地想出解法（实在不行还可以背板子的吧）
-
P3413 萌数
这道题是笔者接触数位dp的第一题，当时学长讲完之后还有点懵，现在发现不是特别难的题目，还是比较套路的
-
P4127 [AHOI2009]同类分布
-
P4317 花神的数论题
相比前面，这道题就显得灵活一些，可能在统计答案的方法上有一些变化，但相信当你做完上面的题之后，这两道题也不在话下！
当然也有些题看起来不是数位dp，但是可能依靠一些数论知识把问题转化成一道数位dp题（比如一些数字本身的性质转化成数字组成的特点），这里就不再过多赘述。
【后记】
数位dp虽然大多在套模板，但是里面的判断和细节还是很多的，多写几道数位dp之后才能发现其中的规律，完全将其掌握。
【特别鸣谢】
本文是笔者听过了两位dalao的讲解后撰写而成
初识数位dp：学长Vergil 【LVYOUYW】
知识巩固：dalao lwz 【lwz2002】
本文发布于洛谷日报，特约作者：Mathison
原文地址：https://www.luogu.org/blog/virus2017/shuweidp
,
