数位dp的定义引自洛谷日报#84：
求出在给定区间\([L,R]\)内，符合条件\(f(i)\)的数\(i\)的个数。条件\(f(i)\)一般与数的大小无关，而与数的组成有关。
由于是按位dp，数的大小对复杂度的影响很小。
由于数位dp状态的上下文信息比较多，所以一般用记忆化搜索实现，而非递推。
P4999 烦人的数学作业
题意简述：\(T\)次询问，每次给定\(L,R\)，输出\([L,R]\)中所有数的数位和之和。
\(1\leq L\leq R\leq 10^{18},1\leq T\leq 20\)
我们发现范围很大，如果模拟会超时。所以引入数位dp的做法，数位dp一般会利用前缀和的思想，把\([L,R]\)转化为\([1,R]-[1,L-1]\)，那么怎么计算\([1,x]\)呢？
用\(f[i][j]\)表示从最高位开始填了\(i\)位，数位和为\(j\)的答案。
思考如何转移：因为我们从最高位开始填，那么显然每一位都有限制。拿\(520\)举例：
- 第\(1\)位如果填\(0\sim 4\)，那么后面可以随便填没有限制。
- 第\(1\)位如果填\(5\)，那么第\(2\)位就要受限，如果填\(0\sim 1\)就和第一条一样，填\(2\)就是第二条，这样循环下去直到填完……
所以\(dfs\)的参数应有三个。
- \(pos\)，表示当前正在填哪一位，从最高位\(len\)（原数的位数）开始往前填，根节点\(pos=len\)，即正在填最高位。\(pos=0\)为结束条件。
- \(limit\)，
bool类型，表示当前这一位有没有限制。 - \(sum\)，表示从最高位填到\(pos+1\)数位和是多少，用作递归结束的返回值。
但是我们发现这样就是一个普通的模拟，把所有数都试了一遍。所以需要记忆化，如果\(f[pos][sum]\)已经计算过了，直接返回即可（需要注意\(limit=false\)时才能用）。
为什么\(limit=false\)才需要记忆化，是因为\(limit=true\)的情况只有\(i=a[pos]\)（见代码），所以在递归树上只是一条链，没有记忆的必要。
至于时间复杂度，那就是状态数量，换句话说就是\(f\)数组的大小，因为调用是\(f[pos][sum]\)，所以大小是\(len*10len\)即\(log_{10}r\)，总\(O(T\ log_{10}r)\)
思考：传递的参数中如果有数组等，为了节省空间，把它定义成全局数组，然后利用回溯传递状态更好（这里的\(pos,sum\)就可以这样子优化掉，但是本身递归层数就不多，所以影响几乎没有）。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int f[25][250],a[25],t,l,r;
int dfs(int pos,bool limit,int sum){
if(pos==0) return sum;
if(!limit&&f[pos][sum]) return f[pos][sum];
int rig=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=rig;i++){
ans=(ans+dfs(pos-1,limit&&i==rig,sum+i))%mod;
//依次枚举这一位填什么
//如果这一位没有限制，那么填前一位也一定没有限制。
//如果这一位有限制，那么只有这一位填的数为a[pos]时才有限制（具体上面有说明）
}
if(!limit) f[pos][sum]=ans;
return ans;
}
int solve(int x){//把x的值存入a数组
int len=0;
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1,0);
}
signed main(){
cin>>t;
while(t--){
cin>>l>>r;
cout<<(solve(r)-solve(l-1)+mod)%mod<<endl;
}
return 0;
}
P2602 [ZJOI2010] 数字计数
与刚才那道很像哦，只不过询问的是\(0\sim 9\)每个数字出现多少次。一个求和，一个计数。
似乎数位dp一般思路就是先写一个暴搜，然后再思考怎么记忆化。一开始想到两种暴搜思路：
- 将状态表示成\(sta[10]\)，为了省空间不再通过参数传递，而是开一个全局，通过回溯实现。传递的参数有\(pos\)和\(limit\)，含义和上面的一样。具体过程也差不多，就是把所有状态枚举一遍。\(pos=0\)时结束，把当前的\(sta\)加入到\(ans\)数组中。最后输出\(ans\)。
- 不用数组表示状态，开三个参数\(pos,limit,cnt\)，其中\(cnt\)表示数字\(x\)的出现次数（与上面的\(sum\)类似，不过一个是求和，一个是计数），\(pos=0\)结束，返回\(cnt\)。主函数中调用\(10\)次\(dfs\)，\(x\)分别取\(0\sim 9\)。调用一次输出一个。
（注：这两种思路都需要处理前导\(0\)的情况，所以上面只是简单的思路，\(dfs\)的形参可能会随需求有增加）
[留坑]
标签：int,sum,pos,limit,例题,dp,数位 From： https://www.cnblogs.com/Sinktank/p/18117420