数位DP

问题：求某个区间[L,R]中满足某种限制条件的数的个数。

暴力的思路：我们可以枚举[L,R]区间内部所有的数，依次判断每个数是否合法，若合法，就记下。

显然，如果数据范围较大，达到10¹⁸甚至更大的级别的时候，这种暴力的算法无论时间还是空间都无法

解决此类问题，所以我们引入数位DP。

所谓数位DP，就是换一种枚举的方式，这种枚举的方式是基于数位（个位，百位，千位...）进行的，与

数的大小没有任何关系。

一般记忆化搜索版本要比数组递推版好实现。

从一道题来引入

（HDU2089）不要62

题意：给定区间，求区间内部不含连续的62和4的数。

数据范围 l,r<=10000000;

我们考虑从最高位开始一位一位的进行枚举，运用记忆化搜索，如果枚举到最后一位所有位都合法，我们就找到了一个数。

思考，前一位什么情况会对后一位的枚举产生影响：

1，这位的前一位是6，这一位枚举了2，那么后面再枚举的情况都不再合法，我们去掉这种情况

2，这一位枚举到4，后面枚举的情况都不合法，我们去掉这种情况。

3，这一位枚举到了范围的最高位，那么下一位枚举的范围不能是0-9，而只能是0-这位的边界。

*在数位DP的记忆化搜索中，记忆化的是穷举0-9的情况，最高位单独枚举并不会产生太大的复杂度。

*数位DP运用到了前缀和的思想，我们统计1-R的答案，在统计1-L-1的答案，相减即为答案。

代码实现来入门数位DP

首先，我们要了解每一位在受到限制的情况下（即前一位枚举到最高位时）枚举的最高位。因此我们要把区间右端点拆分。

1  int pos=0;
2     while(k)
3     {
4         num[++pos]=k%10;
5         k/=10;
6     }

然后就到了数位DP的模板精华部分。

 1 inline int dfs(int pos,int pre,int sta,bool limit)//pos：位数，pre:前驱，sta前一位是否是6，若不是则可以记忆化，否则因
 2                                                   //这一位2不能取而不能记忆化 limit:判断当前位的枚举上限 
 3 {
 4     if(pos==0) return 1;//表示找到了最低位仍合法证明找到了一个数 
 5     if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];//记忆化不是上限的0-9过程 
 6     int up,sum=0;
 7     if(!limit) up=9; else up=num[pos];//判断这位的枚举上限 
 8     for(int i=0;i<=up;i++)//枚举这一位的所有可能 
 9     {
10         if(i==4) continue;//去掉4的情况 
11         if(pre==6&&i==2) continue;//去掉前驱是6，这位是2的情况 
12         sum+=dfs(pos-1,i,i==6,limit&&(i==num[pos]));//搜 
13     }
14     if(!limit) dp[pos][sta]=sum;
15     return sum;
16 }

类似的题还有windy数对于入门可以练习下。

HDU2089完整代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int dp[20][2],num[20];

inline int dfs(int pos,int pre,int sta,bool limit)
{
    if(pos==0) return 1;
    if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];
    int up,sum=0;
    if(!limit) up=9; else up=num[pos];
    for(int i=0;i<=up;i++)
    {
        if(i==4) continue;
        if(pre==6&&i==2) continue;
        sum+=dfs(pos-1,i,i==6,limit&&(i==num[pos]));
    }
    if(!limit) dp[pos][sta]=sum;
    return sum;
}

inline int solve(int k)
{
    int pos=0;
    while(k)
    {
        num[++pos]=k%10;
        k/=10;
    }
    return dfs(pos,0,0,true);
}

int main()
{
    int m,n;
    memset(dp,-1,sizeof(dp));
    while(1)
    {
        scanf("%d%d",&m,&n);
        if(m==0&&n==0) return 0;
        printf("%d
",solve(n)-solve(m-1));
    }
    return 0;
}