最基本的数位dp，
洛谷日报，比较易懂：https://www.luogu.org/blog/virus2017/shuweidp
传参：当前位数pos，记录当前数字出现次数now，当前查找的数字number，是否存在前导0 led，当前是否为枚举上界（最高位）lmt，前面加t的为临时变量
下一位是否达到枚举上界：当前数字达到枚举上界并且这一位也达到上界
下一位数字是否有前导0：该位不为0或没有前导0
在达到枚举上界或者存在前导0的情况下不能记录答案，因为答案没有统计全
最基本的就是这些
#include<iostream> #include<cstring> #include<cstdio> #define ll long long using namespace std; ll a,b; int num[15],len; ll f[15][15]; ll dfs(int pos,int now,int number,bool lmt,bool led){ if(pos==0)return now; if(!lmt && !led && f[pos][now]!=-1)return f[pos][now];//记忆化 ll ans=0; int top=lmt?num[pos]:9,tnow=now; bool tlmt,tled; for(int i=0;i<=top;i++){ tnow=now; if(i==top&&lmt)tlmt=1;else tlmt=0;//达到上限并且是最高位 下一位有最高位限制 if(!led||i)tled=0;else tled=1;//没有前导0或者该位不为0 没有前导0 if((i==number)&&!tled)tnow++;//当前位等于统计的数字并且没有前导0 计入答案 ans+=dfs(pos-1,tnow,number,tlmt,tled); } if(!lmt&&!led)f[pos][now]=ans;//没有前导0且无最高位限制记录当前状态答案 return ans; } ll sol(ll x,int number){ memset(f,-1,sizeof(f)); len=0; while(x){ num[++len]=x%10; x/=10; } return dfs(len,0,number,1,1); } int main(){ scanf("%lld%lld",&a,&b); for(int i=0;i<=9;i++) printf("%lld ",sol(b,i)-sol(a-1,i)); }
原文：https://www.cnblogs.com/superminivan/p/11216148.html