数位DP指一类问题：给定正整数区间[s, e]，问符合条件的数一共有多少个。例如hdu2089以及hdu3555等。 其中，hdu2089的条件为数字中不含4且不含62，hdu3555的条件为数字中包含49。一般而言，这类条件中至少有一个是与整个数的数值无关的，而是与每一位的数字有关。例如上面2道题的条件就与整个数的数值无关。 因此这类问题实际上是数位有关的问题，另一方面，这类问题通常使用DP来加速（因为暴力法几乎肯定超时）。所以称为数位DP。 对于这类问题，大量的解题报告实际上总结出了一个模板，按照这个模板，可以很容易的抓住问题的关键部分以及组织实施代码。 首先对问题做一个变形，原问题很容易变为：问[0, N]区间内符合条件的数一共有多少个。求解的对象只剩下一个，就是N。
以hdu2089为例，令Ai为长度为i的符合条件的数的个数，Bi为长度为i的首位为2的符合条件的数的个数，Ci为长度为i的首位不为2的符合条件的数的个数。很容易写出DP方程。
Ai=Bi+Ci Bi=Ai−1 Ci=8Ci−1+7Bi−1 求出A、B、C以后，就能根据一定的规则进行推导求解。例如考虑N=3812，这是一个4位数，但不能直接采用 A4 作为答案。因为 A4 代表的是区间[0000, 9999]的答案，而不是区间[0000, 3812]的答案（关于前导零的问题，此处不做推敲，因为这里仅仅做一个示意）。 关于N=3812的答案，我们应该这样考虑。假设千位取0，则后3位可以任意取，因此需要将 A3 加入答案；假设千位取1，同理将 A3 加入答案；假设千位取2 ，同理将 A3 加入答案；假设千位取3，此时不能累加 A3 ，需要再考虑百位，而百位需要从0、1、2一直考虑到8；当百位为8时，需要考虑十位…… 这个思路原则上是可以求解的，但是比较繁琐。数位问题是采用DP思想求解的。原则上，DP既可以使用迭代实现，也可以使用递归实现。这一点在数位DP中也是一样的。但是，这里介绍的数位DP的模板是采用递归实现的。这个模板本质上就是能DP的就DP，不能DP的就搜索。 整个模板如下：
typedef long long llt;//这是因为数位问题的结果一般比较大，直接使用longlong llt D[POS][STATUS]; //DP数组，第一维代表数的长度，其他维由具体问题决定 int Dig[POS]; //这个是N分解出的每一位数字 llt dfs(int pos, status, bool lead, bool limit){ if ( -1 == pos ) 根据status返回结果，不是0就是1; if ( !lead && !limit && -1 != D[pos][status] ) return D[pos][status]; int last = limit ? Dig[pos] : 9; llt ans = 0; for(int i=0;i<=last;++i){ ans += dfs(pos-1,newStatus,newLead,limit&&i==last); } return lead || limit ? ans : D[pos][status] = ans; }首先解释一下参数：
llt dfs(int pos, status, bool lead, bool limit)第一个参数代表数位，个位用0表示，十位用1表示……当然个位也可以用1表示，看个人习惯。最后一个参数表示是否受限。例如当 N=3812 ：当千位取3时，百位就是一个受限搜索（意味着百位只能从0~8）；而千位取2时，百位就是不受限的（百位可以从0~9）。 lead 参数代表是否为前导零，这个参数并不总是需要，仅当零会影响结果时需要。什么时候零会影响结果呢？一个基本靠谱的办法就是看条件，条件与零有关，那就会影响结果，就需要 lead 参数，否则就不需要。例如上面说的hdu2089和hdu3555，它们的条件显然与0是无关的，因此就不需要 lead 参数。如果没有 lead 参数，函数体内相应的地方也要做一些修改。这个修改很容易，参看例题。 最重要的参数就是 status ，代表着当前的状态。但状态表示显然与具体题目中的条件有关，因此是无法进行模板化的。另外要注意，状态未必是用1个数表示，可能是2个整型也可能是3个整型，总之，与具体题目有关。同时，这个状态与DP数组的维度基本上是相呼应。如果用1个整型就能表示状态，DP数组就是2维的；如果需要用2个量来表示状态，DP数组可能就是3维的……
if ( -1 == pos ) 根据status返回结果，不是0就是1; if ( !lead && !limit && -1 != D[pos][status] ) return D[pos][status];第一个 if 表示递归结束了。因为我们用 pos=0 表示个位，所以 pos=−1 就表示搜索到底了。此时根据状态返回0或者1，表示找到了一个符合条件的数或者没找到。 第二个 if 是基本的DP递归实现的写法。 另外，return的那句话显然也是DP递归实现的一般写法。
int last = limit ? Dig[pos] : 9;这句话很简单，确定搜索终点。如果不受限就是9，否则就是当前数位上的数字。以 N=3812 的百位为例，如果受限，搜索终点就是8，否则就是9。
llt ans = 0; for(int i=0;i<=last;++i){ ans += dfs(pos-1,newStatus,newLead,limit&&i==last); }这一段就是递归搜索。其中last是刚才确定的。而递归调用中，前后2个参数总是这样写，而 newStatus 参数则要根据status与i共同推得，具体的推导原则显然跟题目有关。至于 newLead 参数，也就是判断是否为前导零，其实非常容易确定，就不赘述了。 有了dfs函数以后，我们还需要一个小小的函数，用于分解N的各位数字，以及第一次调用递归函数。这个小函数就不专门列出了。看例题。
下面来看一个要考虑前导零的例子。这个题目的条件显然是与0有关的。
/* 表示成二进制以后，0比1多认为是合法的 问[s,e]之间有多少个数是合法的 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long llt; //Dij：i表示长度，j表示0与1的数量之差加32 llt D[40][70]; int Dig[100]; //pre表示0比1多多少个，由于可能是负数，为了做数组索引索引加32做一个平移 //lead表示是否前导0 //limit表示是否要限制上界 llt dfs(int pos,int pre,bool lead,bool limit){ //检查一下，是否合法 if ( -1 == pos ) return pre >= 32; //如果没有限制，而且前面已经求出D，则直接返回 if ( !limit && !lead && -1 != D[pos][pre] ) return D[pos][pre]; int last = limit ? Dig[pos] : 1; llt ans = 0; //递归搜索 for(int i=0;i<=last;++i){ if ( lead && 0==i ) ans += dfs(pos-1,pre,true,limit&&(i==Dig[pos])); else ans += dfs(pos-1,pre+(0==i?1:-1),false,limit&&(i==Dig[pos])); } return limit||lead?ans:D[pos][pre]=ans; } //求[1,n]满足条件的数有多少个 llt ddp(llt n){ int k = 0; while(n){ Dig[k++] = n & 1; n >>= 1; } llt tmp = dfs(k-1,32,true,true); return tmp; } int main(){ //freopen("1.txt","r",stdin); memset(D,-1,sizeof(D)); llt a,b; while(2 == scanf("%I64d%I64d",&a,&b)){ printf("%I64d\n",ddp(b)-ddp(a-1)); } return 0; }再看一个与0有关的题目。这个题目的题面明确提到了“不含前导零”，提示需要 lead 参数。但实际上，“相邻数字之差至少为2”这个条件就暗示了需要判断前导零。很简单， 3 这个数是合法的，而003这个数则是非法的。前导零会导致误判断。
/* 条件为相邻两个数字之差至少为2的正整数 问[s,e]之间符合条件的数 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long llt; //Di：i表示长度，j表示最高位 llt D[15][11]; int Dig[100]; //pos表示当前处理的数位，直到0 //pre表示前一位的情况 //lead表示是否为前导0 //limit表示是否要限制上界 llt dfs(int pos,int pre,bool lead,bool limit){ //检查一下，是否合法，本题搜到这里肯定合法 if ( -1 == pos ) return 1; //如果没有限制，而且前面已经求出D，则直接返回 if ( !lead && !limit && -1 != D[pos][pre] ) return D[pos][pre]; int last = limit ? Dig[pos] : 9; llt ans = 0; //递归搜索 for(int i=0;i<=last;++i){ if ( lead ){ if ( 0 == i ) ans += dfs(pos-1,0,true,limit&&i==last); else ans += dfs(pos-1,i,false,limit&&i==last); }else if( pre + 2 <= i || i <= pre - 2 ){ ans += dfs(pos-1,i,false,limit&&i==last); } } return lead||limit?ans:D[pos][pre]=ans; } //求[1,n]满足条件的数有多少个 llt ddp(llt n){ int k = 0; while(n){ Dig[k++] = n % 10; n /= 10; } llt tmp = dfs(k-1,0,true,true); return tmp; } int main(){ //freopen("1.txt","r",stdin); memset(D,-1,sizeof(D)); llt a,b; for(;2==scanf("%lld%lld",&a,&b);){ printf("%lld\n",ddp(b)-ddp(a-1)); } return 0; }再看一个不光是跟数位有关而且跟数值有关的例子。在数位DP下，数值有关的条件也可以归结于数位相关的。如果是题目是纯数值条件的，那也许就是数论的题目，而不是数位DP的题目。 在这道题中，状态就是用3个量表示的，因此DP数组是四维的。
/* 条件为含有13并能被13整除的数 问[s,e]之间有多少个数是符合条件的 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long llt; //Dijk：i表示长度，j表示前一位，k表示余数，w表示是否出现过13 llt D[40][10][13][2]; int Dig[100]; //pos表示当前处理的数位，直到0 //pre表示之前的位 //left表示当前对13的余数 //valid为是否出现过13 //limit表示是否要限制上界 llt dfs(int pos,int pre,int left,bool valid,bool limit){ //检查一下，是否合法 if ( -1 == pos ) return valid&&0==left?1:0; //如果没有限制，而且前面已经求出D，则直接返回 if ( !limit && -1 != D[pos][pre][left][valid] ) return D[pos][pre][left][valid]; int last = limit ? Dig[pos] : 9; llt ans = 0; //递归搜索 for(int i=0;i<=last;++i){ ans += dfs(pos-1,i,(left*10+i)%13,valid||(1==pre&&3==i),limit&&i==last); } return limit?ans:D[pos][pre][left][valid]=ans; } //求[1,n]满足条件的数有多少个 llt ddp(llt n){ int k = 0; while(n){ Dig[k++] = n % 10; n /= 10; } llt tmp = dfs(k-1,0,0,false,true); return tmp; } int main(){ //freopen("1.txt","r",stdin); memset(D,-1,sizeof(D)); llt a; while(1 == scanf("%I64d",&a)){ printf("%I64d\n",ddp(a)); } return 0; }再来看一些状态上更加复杂一点的例子，可能需要用到状态压缩等。当然，这也是DP中常用的技巧。
这个题目应该很容易归结于数位DP，因为除数是各个位上的数字，显然与数位有关。被除数是整个数，也就是数值相关。总的来说，是数位问题。 只需考虑数字2~9即可，数字0、1不必考虑。然后注意到2~9的最小公倍数是2520，就可以把余数做一个有效的记录。
/* 如果一个数能够被自己各个位上的数字整除，就是美丽的 问[s,e]之间美丽的数字有多少个 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long llt; //Dijk：i表示长度，j表示已经出现过的数字，k表示当前的数字值 llt D[20][1<<8][2600]; int Dig[100]; //pos表示当前处理的数位，直到0 //pre表示之前已经出现过的数字，用二进制表示表示 //sum表示当前的数字值 //limit表示搜索的上界 llt dfs(int pos,int pre,int sum,bool limit){ //检查一下，sum是否能整除所有出现过的数位 if ( -1 == pos ) { for(int i=2;i<=9;++i){ if ( (pre&(1<<(i-2))) && (0!=sum%i) ){ return 0; } } return 1; } //如果没有限制，而且前面已经求出D，则直接返回 if ( !limit && -1 != D[pos][pre][sum] ) return D[pos][pre][sum]; int last = limit ? Dig[pos] : 9; llt ans = 0; //递归搜索 for(int i=0;i<=last;++i){ ans += dfs(pos-1,i<2?pre:pre|(1<<(i-2)),(sum*10+i)%2520,limit&&(i==Dig[pos])); } return limit?ans:D[pos][pre][sum]=ans; } //求[1,n]满足条件的数有多少个 llt ddp(llt n){ int k = 0; while(n){ Dig[k++] = n % 10; n /= 10; } return dfs(k-1,0,0,true); } int main(){ //freopen("1.txt","r",stdin); memset(D,-1,sizeof(D)); int nofkase; scanf("%d",&nofkase); llt a,b; while(nofkase--){ scanf("%I64d%I64d",&a,&b); printf("%I64d\n",ddp(b)-ddp(a-1)); } return 0; }这个题目显然是需要 lead 参数的。然后考虑到每个数字有3种情况，没出现过，出现奇数次，出现偶数次，因此考虑使用3进制的状态表示。
/* 条件为每一个奇数数字有偶数个，每一个偶数数字有奇数个 问[s,e]之间符合条件的数 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long llt; typedef unsigned long long ull; int const POW_OF_3[] = { 1,3,9,27,81,81*3,81*9,81*27,81*81,81*81*3 }; //Dijk：i表示长度，j表示对应数字的出现情况，使用3进制表示，0表示没有，1表示奇数，2表示偶数 llt D[22][59100]; int Dig[100]; //pos表示当前处理的数位，直到0 //pre表示之前的情况 //lead表示是否为前导0 //limit表示是否要限制上界 llt dfs(int pos,int pre,bool lead,bool limit){ //检查一下，是否合法 if ( -1 == pos ) { //pre%3如果是0就不必讨论，否则i为奇数时余数必须是2，i为偶数时余数必须是1 for(int i=0;pre;++i,pre/=3){ if ( ( pre % 3 ) && ( ( pre % 3 ) & 1 ) == ( i & 1 ) ){ return 0; } } return 1; } //如果没有限制，而且前面已经求出D，则直接返回 if ( !lead && !limit && -1 != D[pos][pre] ) return D[pos][pre]; int last = limit ? Dig[pos] : 9; llt ans = 0; //递归搜索 int tmp = 0, npre; for(int i=0;i<=last;++i){ if ( lead && 0 == i ) ans += dfs(pos-1,pre,true,limit&&i==Dig[pos]); else { npre = pre; tmp = npre / POW_OF_3[i] % 3; npre -= tmp * POW_OF_3[i]; if ( 2 == tmp ) tmp = 1; else tmp += 1; npre += tmp * POW_OF_3[i]; ans += dfs(pos-1,npre,false,limit&&i==Dig[pos]); } } return lead||limit?ans:D[pos][pre]=ans; } //求[1,n]满足条件的数有多少个 llt ddp(ull n){ int k = 0; while(n){ Dig[k++] = n % 10; n /= 10; } llt tmp = dfs(k-1,0,true,true); return tmp; } int main(){ //freopen("1.txt","r",stdin); memset(D,-1,sizeof(D)); int kase; scanf("%d",&kase); ull a,b; while(kase--){ scanf("%llu%llu",&a,&b); printf("%lld\n",ddp(b)-ddp(a-1)); } return 0; }最后看两个可以转为数位DP的例子。这两个题目通过找规律配合一些数组什么的也都是可以做的。
这个题目问数字1出现的次数，可以通过找规律然后直接统计计算得出。这里把它转成数位DP问题，即回答以下9个数位问题：包含1个1的数有多少个，包含2个1的数有多少个…… 当然，这个做法速度上应该有点影响。
/* N以内1的数量是多少个 求出[1,N]区间内包含1个1的数有多少个 2个1的数有多少个…… 最后累加。 数位DP */ #include <string.h> #include <iostream> using namespace std; typedef long long llt; llt D[12][11][11]; int Dig[30]; int K; llt dfs(int pos,int sum,bool limit){ if ( -1 == pos ) return sum==K; if ( !limit && -1 != D[pos][sum][K] ) return D[pos][sum][K]; llt last = limit ? Dig[pos] : 9; llt ans = 0; for(int i=0;i<=last;++i){ ans += dfs(pos-1,sum+(1==i),limit&&i==last); } return limit ? ans : D[pos][sum][K] = ans; } llt ddp(llt n){ int k = 0; while( n ){ Dig[k++] = n % 10; n /= 10; } llt ans = 0; for(int i=1;i<=k;++i) K=i,ans+=i*dfs(k-1,0,true); return ans; } int main(){ memset(D,-1,sizeof(D)); llt n; cin >> n; cout<<ddp(n)<<endl; return 0; }这个题目要求统计0~9的数量，上一题实际上是统计1的数量。所以，在上一题的基础上改改就行，传个参数。
/* [s,e]区间内0-9数字出现的次数 统计含1个1的数有几个，2个1的数有几个…… */ #include <string.h> #include <iostream> using namespace std; typedef long long llt; //dijkw，i表示数位，j表示数字，k表示已有的数量，w表示目标数量 llt D[20][10][20][20]; int Dig[30]; int K,Digit; llt dfs(int pos,int cnt,bool lead,bool limit){ if ( -1 == pos ) return cnt==K; if ( !lead && !limit && -1 != D[pos][Digit][cnt][K] ) return D[pos][Digit][cnt][K]; llt last = limit ? Dig[pos] : 9; llt ans = 0; for(int i=0;i<=last;++i){ if ( lead && 0==i ) ans += dfs(pos-1,0,true,limit&&i==last); else ans += dfs(pos-1,cnt+(Digit==i),false,limit&&i==last); } return lead || limit ? ans : D[pos][Digit][cnt][K] = ans; } llt proc(llt n){ int k = 0; while( n ){ Dig[k++] = n % 10; n /= 10; } llt ans = 0; for(int i=1;i<=k;++i) K=i,ans+=i*dfs(k-1,0,true,true); return ans; } int main(){ memset(D,-1,sizeof(D)); llt a,b; cin >> a >> b; for(Digit=0;Digit<10;++Digit){ cout<<proc(b)-proc(a-1)<<endl; } return 0; }数位DP模板是一个很好的模板。因为它首先给定了代码组织实施的框架，这里面就包含了状态转移的实现；更重要的是这个框架将DP中另一个核心问题“状态的设计”单独抽了出来，对每一个问题只需要单独考虑状态即可，很容易抓住重点去进行考虑和实现。 在此基础上进行一定的修改，还有可能完成更复杂的跟数位有关的问题。
