数位DP套路化写法

数位DP

引入

数位动态规划（数位DP）主要用于解决 “在区间[ l , r ] [l, r][l,r]这个范围内，满足某种约束的数字的数量、总和、平方” 这一类问题

针对这类问题，有两类写法，一种是记忆化搜索写法，一种是迭代写法。

力推记忆化搜索写法，原因如下：

• 记搜写法容易举一反三、易编码
  • 预处理后的迭代写法，往往边界条件很多，状态转移方程容易写错或漏项，其边界容易漏判误判；且不同题目时，迭代写法的DP过程变化较大，而记搜的dfs框架则非常套路，容易举一反三。

数位dp有个通用的套路，就是先采用前缀和思想，将求解 “[l, r]这个区间内的满足约束的数的数量” ，转化为 “[1, r]满足约束的数量 - 区间[1, l - 1]满足约束的数量 ”

所以我们最终要求解的问题通常转化为：[ 1 , x ] [1, x][1,x]中满足约束的数量，或者[ 0 , x ] [0, x][0,x]中的满足约束的数量 （左边界取决于题目）

然后将数字x xx拆分为一个个数位

数位，如个位、十位、百位等，单个数码（比如十进制，此处就是指0 ~ 9）在数x xx中所占据的一个位置

在代码中表现为：

• a [ 1 ⋯ l e n ] a[1 \cdots len]a[1⋯len]：将数x xx分解为R RR进制（一般为十进制或者二进制），用数组存储，a [ i ] a[i]a[i]表示x xx在R i − 1 R^{i-1}Ri−1处的系数
• 即x xx这个数的长度为l e n lenlen，最高位上的数字为a [ l e n ] a[len]a[len]，最低位上的数字为a [ 1 ] a[1]a[1]
• 比如十进制数字4321，转化为a aa数组后，a 4 = 4 , a 3 = 3 , a 2 = 2 , a 1 = 1 a_4 = 4, a_3 = 3, a_2 = 2, a_1 = 1a4​=4,a3​=3,a2​=2,a1​=1

typedeflonglongLL;LLsolve(LL x){intlen=0;while(x>0){a[++len]=x%10;x/=10;}returndfs(...);//记忆化搜索}

接下来考虑填数，高位往低位填，即l e n → 1 len \to 1len→1

借助一道经典的题目来感受下dp的大致过程

例题0：洛谷 P4999 烦人的数学作业

求解区间[ L , R ] [L, R][L,R]中所有数的数位和之和

数位和：一个数的所有数位上的数字加起来的和，比如313的数位和为3 + 1 + 3 = 7 3+1+3=73+1+3=7

共1 ≤ T ≤ 20 1 \le T \le 201≤T≤20组数据，其中1 ≤ L ≤ R ≤ 10 18 1 \le L \le R \le 10^{18}1≤L≤R≤1018

既然叫做记搜，也就是就是层层深入，每一层搜索填写一个数，记忆化搜索函数d f s dfsdfs中，我们用形参p o s pospos来表示当前需要填写的位置

• p o s pospos：int型变量，表示当前枚举的位置，一般从高到低

话说回来，我们需要计算的是[ 0 , x ] [0, x][0,x]的所有数的数位和之和

虽然区间范围的左边界最小为1，但是我们发现0对答案没有贡献，所以我们把范围看成[ 0 , x ] [0, x][0,x]也无妨，

我们需记录一个变量l i m i t limitlimit，表示当前数位是否可以任意填写

故在记忆化搜索函数d f s dfsdfs的常设定的形参加上l i m i t limitlimit

• l i m i t limitlimit：bool型变量，表示枚举的第p o s pospos位是否受到限制，
  • 为 true 表示取的数不能大于a [ p o s ] a[pos]a[pos]，而只有在[ p o s + 1 , l e n ] [pos + 1, len][pos+1,len]的位置上填写的数都等于a [ i ] a[i]a[i]时该值才为 true
  • 否则表示当前位没有限制，可以取到[ 0 , R − 1 ] [0, R - 1][0,R−1]，因为R RR进制的数中数位最多能取到的就是R − 1 R - 1R−1

dfs函数的形参还需要添加：

• sum：int型变量，表示当前l e n → ( p o s + 1 ) len \to (pos + 1)len→(pos+1)的数位和

这种普通的dfs搜索，其过程就像是一棵 “满多叉树” ，时间复杂度最坏为O ( 10 l e n ) O(10^{len})O(10len)，其中len最大值为 19（1e18有 19 位），这显然不能接受

而动态规划就是减少冗余的重复计算，也就是我们将这棵 “满多叉树” 中相同的子树部分给删除掉，从而来优化时空复杂度

设状态f [ p o s ] [ s u m ] f[pos][sum]f[pos][sum]表示：

• 位置[ p o s + 1 , l e n ] [pos + 1, len][pos+1,len]都已填写完毕，且这些数位之和为sum的情况下，数位[ 1 , p o s ] [1, pos][1,pos]任意填写（即limit为false）
• f [ p o s ] [ s u m ] f[pos][sum]f[pos][sum]为满足约束的所有数的数位和之和

故我们可以大致写出记忆化搜索的代码了：

其中f ff数组初始化均为− 1 -1−1，而∼ f [ p o s ] [ n u m ] \sim f[pos][num]∼f[pos][num]是按位取反操作，当值等于− 1 -1−1时返回0 00，也就是判断值是否为− 1 -1−1

LLdfs(intpos,boollimit,intsum){if(!pos)//递归边界returnsum;if(!limit&&~f[pos][sum])//没限制并且dp值已搜索过returnf[pos][sum];intup=limit?a[pos]:9;LL res=0;for(inti=0;i<=up;i++)res=(res+dfs(pos-1,limit&&i==up,sum+i))%md;if(!limit)//记搜，可复用f[pos][sum]=res;returnres;}

然后再solve中调用dfs函数

LLsolve(LL x){intlen=0;while(x>0){a[++len]=x%10;x/=10;}returndfs(len,true,0);//初始状态可以理解为len之前全部卡前导0的上}

两个问题

• 问题1：怎么证明这个记忆化搜索的优化了原先的时间复杂度？
• 问题2：为什么状态需要设置为不受l i m i t limitlimit限制的前提下？
  

完整代码参考

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constexprintN=20,md=1e9+7;inta[N];LL f[N][9*18+5];// f[pos][sum]：在[pos + 1, len]中的数位和为sum，[1, pos]的数位任意填。满足这样约束的数的总和// 总共最多 19 * (9 * 18)个状态LLdfs(intpos,boollimit,intsum){if(!pos)//递归边界returnsum;if(!limit&&~f[pos][sum])//没限制并且dp值已搜索过returnf[pos][sum];intup=limit?a[pos]:9;LL res=0;for(inti=0;i<=up;i++)res=(res+dfs(pos-1,limit&&i==up,sum+i))%md;if(!limit)//记搜，可复用f[pos][sum]=res;returnres;}LLsolve(LL x){intlen=0;while(x>0){a[++len]=x%10;x/=10;}returndfs(len,true,0);//初始状态可以理解为len之前全部卡前导0的上}intT;intmain(){cin.tie(0)->sync_with_stdio(false);memset(f,-1,sizeoff);//可复用的，多组样例都可使用cin>>T;while(T--){LL l,r;cin>>l>>r;LL ans=(solve(r)-solve(l-1)+md)%md;if(ans<0)ans+=md;cout<<ans<<'\n';}}

概述

在上述例题0中，我们已经知道了数位dp的过程，我们往往把约束设置为形参和动态规划的状态

以下为记忆化搜索函数d f s dfsdfs的常设定的形参

• p o s pospos：int型变量，表示当前枚举的位置，一般从高到低
• l i m i t limitlimit：bool型变量，表示枚举的第p o s pospos位是否受到限制，
  • 为true表示取的数不能大于a [ p o s ] a[pos]a[pos]，而只有在[ p o s + 1 , l e n ] [pos+1, len][pos+1,len]的位置上填写的数都等于a [ i ] a[i]a[i]时该值才为true
  • 否则表示当前位没有限制，可以取到[ 0 , R − 1 ] [0, R-1][0,R−1]，因为R RR进制的数中数位最多能取到的就是R − 1 R-1R−1
• l a s t lastlast：int型变量，表示上一位（第p o s + 1 pos+1pos+1位）填写的值
  • 往往用于约束了相邻数位之间的关系的题目
• l e a d 0 lead0lead0：bool型变量，表示是否有前导零，即在l e n → ( p o s + 1 ) len \to (pos+1)len→(pos+1)这些位置是不是都是前导零
  • 基于常识，我们往往默认一个数没有前导零，也就是最高位不能为0，即不会写为000123，而是写为123
  • 只有没有前导零的时候，才能计算0的贡献。
  • 那么前导零何时跟答案有关？
    • 统计0的出现次数
    • 相邻数字的差值
    • 以最高位为起点确定的奇偶位
• s u m sumsum：int型变量，表示当前l e n → ( p o s + 1 ) len \to (pos+1)len→(pos+1)的数位和
• r rr：int型变量，表示整个数前缀取模某个数m mm的余数
  • 该参数一般会用在：约束中出现了能被m mm整除
  • 当然也可以拓展为数位和取模的结果
• s t stst：int型变量，用于状态压缩
  • 对一个集合的数在数位上的出现次数的奇偶性有要求时，其二进制形式就可以表示每个数出现的奇偶性

练习题

通过例题来应用中掌握非常套路化的数位dp过程

P2602 [ZJOI2010] 数字计数

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constexprintN=20;inta[N];intdigit;//当前需要统计的数字// f[pos][cnt][0/1]：当最高位已经填了（没有前导0时）在[pos + 1, len]中digit填了cnt个，[1, pos]任意填，digit出现的次数// 第三维0表示digit=0,第三维为1表示digit!=1// 当limit=false时，容易知道填1-9的数量是相同的LL f[N][N][2],ans[10];LLdfs(intpos,boollimit,boollead0,intcnt){if(!pos)// 递归边界returncnt;auto&now=f[pos][cnt][digit!=0];if(!limit&&!lead0&&~now)// 没限制并且dp值已搜索过returnnow;intup=limit?a[pos]:9;LL res=0;for(inti=0;i<=up;i++){//填0的时候需注意是否为前导//前导零不算入0的个数if(lead0&&digit==0&&i==0){res+=dfs(pos-1,limit&&i==up,lead0&&i==0,0);}else{if(i==digit)res+=dfs(pos-1,limit&&i==up,lead0&&i==0,cnt+1);elseres+=dfs(pos-1,limit&&i==up,lead0&&i==0,cnt);}}if(!limit&&!lead0)//无限制并且没有前导0now=res;returnres;}voidsolve(LL x,intf){intlen=0;while(x>0){a[++len]=x%10;x/=10;}for(inti=0;i<=9;i++){digit=i;ans[i]+=f*dfs(len,1,1,0);}}intmain(){memset(f,-1,sizeoff);LL l,r;cin>>l>>r;solve(r,1);//加上[1, r]solve(l-1,-1);//扣除掉[1, l-1]for(inti=0;i<=9;i++)cout<<ans[i]<<' ';}