数位DP

数位DP问题

用来解决一类对数位进行某种计数的问题，通常有以下特点：

• 统计满足某种条件或约束的数量，且需要统计的区间跨度极大
• 某些条件或约束可以利用数位拆分的方式去满足
• 通常给定的区间 $[l,r]$ 可以拆分为 $[1,l],[1,r]$ 然后利用前置和做差计算

因为需要满足的约束以及边界条件较难进行完整判断，所以设计状态转移方程进行迭代很难成功

这里采用记忆化搜索的方式进行计算

例题一：https://www.luogu.com.cn/problem/P4999

给出一个区间 $[l,r]$ ，求 $l$ 到 $r$ 区间内每个数的数位和

const int mod=1e9+7;

LL dp[32][400];

LL dfs(int pos,bool lim,LL sum,int a[]){
    if (pos==0) return sum;
    if (!lim&&dp[pos][sum]!=-1) return dp[pos][sum];
    int k=lim?a[pos]:9;
    LL res=0;
    for (int i=0;i<=k;i++)
        res=(res+dfs(pos-1,lim&&i==k,sum+i,a))%mod;
    if (!lim) dp[pos][sum]=res;
    return res;
}

LL work(LL x){
    memset(dp,-1,sizeof dp);
    int idx=0,a[32];
    while (x){
        a[++idx]=x%10;
        x/=10;
    }
    return dfs(idx,1,0,a);
}

void solve(){
    LL l,r;
    cin>>l>>r;
    cout<<(work(r)-work(l-1)+mod)%mod<<endl;
}

记一个数的数位和为 $sum_x$ ，题意转化为求解 $\sum_{i=l}^r sum_i$ ，满足前缀和性质，则可以分解为求解 $\sum_{i=0}^r sum_i-\sum_{i=0}^{l-1} sum_i$

DFS 需要的参数有 $pos,lim,sum$ ，其中 $pos$ 表示当前枚举到了哪一个数位，$lim$ 表示当前位是否被上一位约束，$sum$ 表示枚举到第 $pos$ 位前数位和为 $sum$

逐行分析代码：

LL dfs(int pos,bool lim,LL sum,int a[]){
    if (pos==0) return sum;//从大到小枚举位，第0位递归终点返回sum
    if (!lim&&dp[pos][sum]!=-1) return dp[pos][sum];
    //如果当前位没有被约束，且曾经记录过当前的状态，那么直接使用
    int k=lim?a[pos]:9;//判断当前位能枚举到的上界
    //如果存在约束，这一位最大只能填到a的第pos位上的数，否则可以填到9
    LL res=0;
    for (int i=0;i<=k;i++)//枚举
        res=(res+dfs(pos-1,lim&&i==k,sum+i,a))%mod;
    //lim&&i==k表示约束的传递
    if (!lim) dp[pos][sum]=res;//如果这一位没有限制，那么将这个状态记忆化
    return res;
}

约束的传递：假如有一个数为 $8234$ ，从第四位开始枚举，因为枚举的所有数不能超过 $8234$ ，那么所有数的第四位也不应该超过 $8$

约束值一开始传入为 $1$ ，那么第四位就被约束到了 $[0,8]$ 。当枚举第三位时，如果第四位填的是 $8$ ，显然第三位就不能超过 $2$ ，如果第四位填的是 $[0,7]$ ，则第三位可以任填。

lim&&i==k 体现了传递性，只有上一位被约束后，下一位才会有被约束的资格

因为这道题中，前导 $0$ 对答案无贡献，所以无需考虑前导 $0$ 带来的影响

LL dp[32][400];

记忆化的 $dp_{i,j}$ 表示在无约束的情况下填到第 $i$ 位且前 $i$ 位的数位和为 $j$ 时 $[1,i]$ 位满足约束的所有数的数位和

为什么只有在没有约束的条件下才进行记忆？

因为如果当前位存在约束，那么之后的状态都不是共用的，即存在某些状态不合法，无法从这些状态转移

例题二：https://www.luogu.com.cn/problem/P2602

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

LL dp[20][2][20][2];

LL dfs(int pos,bool lim,bool zro,int cnt,int dig,int a[]){
    if (!pos) return cnt;
    if (dp[pos][lim][cnt][zro]!=-1) return dp[pos][lim][cnt][zro];
    LL res=0;
    int k=lim?a[pos]:9;
    for (int i=0;i<=k;i++){
        if (zro)
            res+=dfs(pos-1,lim&&i==k,zro&&i==0,i==dig&&dig!=0?cnt+1:cnt,dig,a);
        else
            res+=dfs(pos-1,lim&&i==k,0,i==dig?cnt+1:cnt,dig,a);
    }
    dp[pos][lim][cnt][zro]=res;
    return res; 
}

LL work(LL x,int dig){
    int idx=0,a[20];
    memset(dp,-1,sizeof dp);
    while(x){
        a[++idx]=x%10;
        x/=10;
    }
    return dfs(idx,1,1,0,dig,a);
}

void solve(){
    LL a,b;
    cin>>a>>b;
    for (int i=0;i<=9;i++)
        cout<<work(b,i)-work(a-1,i)<<' ';
}

这道题中，需要对 $0$ 进行计数，因为前导 $0$ 不能参与计数，所以需要考虑这一因素

那么 DFS 传入的参数有：$pos,lim,zro,cnt,dig$ ，$zro$ 表示当前位前是否有前导 $0$ ，$cnt,dig$ 表示 $pos$ 位前，数位为 $dig$ 的数量

for (int i=0;i<=k;i++){
    if (zro)//如果存在前导0
        res+=dfs(pos-1,lim&&i==k,zro&&i==0,i==dig&&dig!=0?cnt+1:cnt,dig,a);
        //zro&&i==0表示前导0的传递，与约束的传递类似
        //dig为0时，如果存在前导0且当前填0，则需要刨去这一次的计数
    else
        res+=dfs(pos-1,lim&&i==k,0,i==dig?cnt+1:cnt,dig,a);
}

这里记忆化的 $dp$ 有四维空间，即把 DFS 的所有参数都记录下来，虽然有部分参数可以根据对答案的影响进行压缩，但在空间允许的条件下，这种方式可以减少思考过程

LL dp[20][20][2];

LL dfs(int pos,bool lim,bool zro,int cnt,int dig,int a[]){
    if (!pos) return cnt;
    if (!lim&&dp[pos][cnt][zro]!=-1) return dp[pos][cnt][zro];
    LL res=0;
    int k=lim?a[pos]:9;
    for (int i=0;i<=k;i++){
        if (zro)
            res+=dfs(pos-1,lim&&i==k,zro&&i==0,i==dig&&dig!=0?cnt+1:cnt,dig,a);
        else
            res+=dfs(pos-1,lim&&i==k,0,i==dig?cnt+1:cnt,dig,a);
    }
    if (!lim) dp[pos][cnt][zro]=res;
    return res; 
}

上面为压缩空间后的函数，只有不存在约束时，产生的结果才会被转移，所以每次 DFS 后都根据 $lim$ 判断是否记录

例题三：https://www.luogu.com.cn/problem/P2657

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

int dp[20][20];

int dfs(int pos,int lim,int zro,int p,int a[]){
    if (!pos) return 1;
    if (!lim&&!zro&&p!=11&&dp[pos][p]!=-1) return dp[pos][p];
    int res=0;
    int k=lim?a[pos]:9;
    for (int i=0;i<=k;i++){
        if (zro)
            res+=dfs(pos-1,lim&&i==k,zro&&i==0,i==0?p:i,a);
        else if (abs(i-p)>=2)
            res+=dfs(pos-1,lim&&i==k,0,i,a);
    }
    if (!lim&&!zro&&p!=11) dp[pos][p]=res;
    return res;
}

int work(int x){
    int idx=0,a[20];
    memset(dp,-1,sizeof dp);
    while (x){
        a[++idx]=x%10;
        x/=10;
    }
    return dfs(idx,1,1,11,a);
}

void solve(){
    int a,b;
    cin>>a>>b;
    cout<<work(b)-work(a-1)<<endl;
}

这道题引入了一个新的约束条件：相邻两位数之差为 $2$，参数也要新设置一个 $p$ 表示前一位填的数

另外在进入 DFS 时需要对 $p$ 的初值进行设置， 因为一开始枚举的 $pos$ 没有前一位，所以要设置一个不约束最高位的值，即 $\lvert p-a_{top}\rvert \ge 2$

浅谈在实现数位DP中迭代法与记忆化搜索的优劣性

迭代法主要依赖预处理后的 $dp_{i,j,\cdots}$ ，在约束很多时，边界条件也会增多，状态转移方程易写错或写漏

记忆化搜索在面对不同题时，需要变化的部分不多，无非是对 DFS 参数的设置以及向下搜索的特判

理论上这两种方式的时间复杂度相同，都会将所有状态仅访问一遍，但记忆化搜索需要调用多次递归，常数可能略大于迭代实现的常数

时间复杂度通常为：$O(\log n\times k)$ ，$k$ 表示限制条件，总时间复杂度为 $O(N)$ ，$N$ 为所有状态数