竞赛中有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。

通常的数位dp可以写成如下记忆化搜索的形式:

1 int dfs(int i, int s, bool e)  2 { 3     if (i==-1) return s==target_s;  4     if (!e && ~f[i][s]) return f[i][s]; 5     int res = 0; 6     int u = e?num[i]:9; 7     for (int d = first?1:0; d <= u; ++d) 8         res += dfs(i-1, new_s(s, d), e&&d==u); 9     return e?res:f[i][s]=res;10 }

 

从左到右位数编号依次减小，最右位编号为0。

其中：

   　f为记忆化数组;f[i][s]表示第i位左边已枚举好的数包含了状态s的情况下，i 到 0 位组成的数中有几个满足条件的数；

   　i为当前处理串的第i位（权重表示法，也即后面剩下i+1位待填数）；

      s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）；

   　e表示之前的数是否是上界的前缀（即后面的数枚举上界能否任意填）。

   　for循环枚举数字时，要注意是否能枚举0，以及0对于状态的影响，有的题目前导0和中间的0是等价的，但有的不是，对于后者可以在dfs时再加一个状态变量z，表示前面是否全部是前导0，   也可以看是否是首位，然后外面统计时候枚举一下位数。

注意：

　　不满足区间减法性质的话（如hdu 4376），不能用solve(r)-solve(l-1)，状态设计会更加诡异。

【例题】         在[L , R] 的正整数区间内，要么包含3 要么包含 8（3和8不能同时存在于一个数中） 的不同的整数有多少个？【解】 　　　首先[l , r] = [1 , r] - [1 , l - 1]。因此只要能计算 [ 1 , x ] 即可　　　这是个数位dp，加上状态压缩 —— （0 --无3无8 ， 1-- 有3无8 ， 2 --无3有8 ， 3 --3、8同时存在）

 

下面是关键代码：

 

1 int new_s(int s , int d)    2 { 3     //根据枚举出来的d,获得当前情况的状态值,用于递归 4     if (d == 3) return s | 1; 5     if (d == 8) return s | 2; 6     return s; 7 } 8 int dfs(int i, int s, bool e) 9 {10     if (i==-1) return s==1 || s == 2; //如果s==3说明3、8同时存在，所以个数是011     if (!e && ~f[i][s]) return f[i][s];12     int res = 0;13     int u = e?num[i]:9;14     for (int d = 0; d <= u; ++d)15         res += dfs(i-1, new_s(s, d), e&& (d==u) );16     return e?res:f[i][s]=res;17 }

 

　　头一次写这种代码，开始有点不明白，其实想了下，就是递归搜索加上结果记忆化，它的奇特就在于多了个状态的更新和传递而已。