数位dp

(本文参考于 大佬博客)

数位dp是一种高速求解给定区间内符合一定条件的数的个数的算法。其基本思想为记忆化搜索。

数位dp一般应用于：

  1. 求出在给定区间[A,B]内，符合条件P(i)的数i的个数.

  2. 条件P(i)一般与数的大小无关，而与 数的组成 有关

求解的基本步骤如下：

  1. 当我们求 [ 0 , 100000 ] 和 [ 100001 , 200000 ]中符合条件的数的个数时，我们只需要求出前一个区间符合条件的数的个数，后面的区间只需要使用前面计算出来的值就可以了。

  2. 以下面的 不含49 为例，当我们在求[ 49001 , 50000 ]符合条件的数的个数时，会有不符合条件的情况存在，因此我们需要对其值进行判断，即将这一部分的值省略掉，当把这部分去掉之后，我们再求出来[ 0 , 100000 ]中符合条件的数的个数。

  3. 如果 b 为 123456 ，如果我们仍然求解[100001,200000]的话就会出错，我们只能先求解[100000,120000]，然后再求解[120001,123000]，因此，我们还需要判断当前是否是数的上限。

不含49

求[ a , b ]中不包含49的数的个数。

1<=a<=b<=1e9

代码如下：


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a,b;
int num[20];//储存每一位的值
int dp[20][2];//储存长度为length时符合条件的数的数量，两个数组分别表示 是4时 和 不是4时 的数量

int dfs(int length,bool is_4,bool is_max){
    //如果计算到最后一位，那么直接返回
    if(length==-1) return 1;
    
    //如果不是数的上限并且之前计算过，这步就是记忆化最关键的一步
    if(!is_max && dp[length][is_4]) return dp[length][is_4];
    
    int cnt=0,maxx=(is_max ? num[length]:9);//判断是否是上限，即判断当前位所能取到的值的范围
    for(int i=0;i<=maxx;i++){
        if(is_4 && i==9) continue;//上一位是4，这一位是9，那么就直接跳过
        cnt+=dfs(length-1,i==4,is_max && i==maxx);
    }
    
    //如果是上限，那么不能保存，因为dp保存的是[100000,200000]这样的值，并不能储存[100000,120000]的值
    return is_max?cnt:dp[length][is_4]=cnt;
}

int solve(int x){
    memset(num,0,sizeof(num));
    int length=0;
    while(x){
        num[length++]=x%10;
        x/=10;
    }
    return dfs(length-1,false,true);
}
int main()
{
    scanf("%d %d",&a,&b);
    printf("%d\n",solve(b)-solve(a-1));
    return 0;
}