解决问题：询问区间 $[l, r]$ 内数位间满足某种关系的数的个数。

模板：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+5;

/**
pos：数位位置
pre：前一位数
st：当前状态 
lead：前导零
limit：最高位标记
dp：当前状态个数
*/
ll dfs(int pos, int pre, int st, ……, int lead, int limit) //记搜
{
    if(pos > len) return st; //剪枝
    if(dp[pos][pre][st]……[……]!=-1 && !limit && !lead) return dp[pos][pre][st]……[……];//记录当前值
    ll ret = 0; //暂时记录当前方案数
    int res = limit ? a[len-pos+1] : 9; //res当前位能取到的最大值
    for(int i=0; i<=res; i++) {
        if(!i && lead) ret += dfs(……, ……, ……, i==res&&limit); //有前导0并且当前位也是前导0
        else if(i && lead) ret += dfs(……,……,……, i==res&&limit); //有前导0但当前位不是前导0，当前位就是最高位
        else if(根据题意而定的判断) ret += dfs(……, ……, ……, i==res&&limit);
    }
    if(!limit && !lead) dp[pos][pre][st]……[……] = ret; //当前状态方案数记录
    return ret;
}
ll part(ll x)//把数按位拆分
{
    len = 0;
    while(x) a[++len] = x%10, x /= 10;
    memset(dp,-1,sizeof dp); //初始化-1（因为有可能某些情况下的方案数是0）
    return dfs(……, ……, ……, ……); //进入记搜
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&l,&r);
        if(l) printf("%lld",part(r)-part(l-1));//[l,r](l!=0)
        else printf("%lld",part(r)-part(l));//从0开始要特判
    }
    return 0;
}

例题

不要62

题意

询问区间内不含数字4且没有连续的62的数字个数。

题解

首先分析要用到的状态（dfs传的参数）。

前导零不需要，只用当前位和上一位即可判断数字是否满足条件，所以只用pos,pre,limit三个参数即可。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+5;

int len, a[55], dp[10][10];
LL dfs(int pos, int pre, int limit){
    if(pos > len) return 1;
    if(dp[pos][pre]!=-1 && !limit) return dp[pos][pre];
    int ret = 0, res = limit ? a[len-pos+1] : 9;
    for(int i=0; i<=res; i++){
        if(i == 4 || (i == 2 && pre == 6)) continue;
        ret += dfs(pos+1, i, i==res&&limit);
    }
    if(!limit) dp[pos][pre] = ret;
    return ret;
}
LL solve(LL x){
    len = 0;
    while(x) a[++len] = x%10, x/=10;
    memset(dp, -1, sizeof dp);
    return dfs(1, 0, 1);
}
int n, m;
int main(){
    while(scanf("%d%d", &n, &m) && (n+m)){
        printf("%lld\n", solve(m)-solve(n-1));
    }
}

windy数

题意

询问区间内满足任意两个相邻数字之差都不小于2且不含前导零的数的个数。

题解

题目要求不要前导零，所以必须要有lead参数。

要想判断数字是否满足条件，只需要当前数和上一个判断差是否大于等于2即可。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+5;

int len, a[55], dp[50][50];
LL dfs(LL pos, LL pre, bool lead, bool limit){
    if(pos > len) return !lead;
    if(dp[pos][pre]!=-1 && !limit && !lead) return dp[pos][pre];
    LL ret = 0; int res = limit ? a[len-pos+1] : 9;
    for(int i=0; i<=res; i++){
        if(!i && lead) ret += dfs(pos+1, i, 1, i==res&&limit); // i == 0
        else if(i && lead) ret += dfs(pos+1, i, 0, i==res&&limit); //i != 0
        else if(abs(i-pre)>=2) ret += dfs(pos+1, i, 0, i==res&&limit);
    }
    if(!limit && !lead) dp[pos][pre] = ret;
    return ret;
}
LL solve(LL x){
    len = 0;
    while(x) a[++len] = x%10, x/=10;
    memset(dp, -1, sizeof dp);
    return dfs(1, 0, 1, 1);
}
int n, m;
int main(){
    while(~scanf("%d%d", &n, &m) && (n+m)){
        printf("%lld\n", solve(m)-solve(n-1));
    }
}

数字计数

题意

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

题解

解法一

转化成求 1 到 n 之间 x 出现的次数。

因为题目没有要求数位之间的联系，pre可以不用要。lead 和 limit 肯定是需要的。

对数字间没有要求，所以不用考虑数位间的关系，要考虑的是 x 出现的次数。

因为要记忆化，所以考虑加上一个状态量，

解法二

其实这道题不用数位dp也能做，题目让求[1, n]范围内数字x出现的次数，直接观察规律统计答案即可。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL count(LL n, LL x) {
    LL cnt = 0, k;
    for (LL i=1; k=n/i; i*=10) {
        LL high = k / 10; // 高位的数字。
        if(x == 0) {
            if(high) high--;
            else break;
        }
        cnt += high * i;
        LL cur = k % 10; // 当前位的数字。
        if (cur > x) cnt += i;
        else if (cur == x) cnt += n-k*i+1; // n - k*i 为低位的数字。
    }
    return cnt;
}
LL n, m;
int main(){
    while(~scanf("%lld%lld", &n, &m) && (n+m)){
        for(int i=0; i<=9; i++)
            printf("%lld%c", count(m, i)-count(n-1, i), " \n"[i==9]);
    }
}

参考

数字组成的奥妙——数位dp

计算1至n中数字X出现的次数