数字计数--数位dp

1.不考虑前导零

2.每一位计数，就是有点“数页码”的意思

P2602 [ZJOI2010] 数字计数 - 洛谷

相关题目：记得加上前导零

数页码--数位dp-CSDN博客

https://blog.csdn.net/2301_80422662/article/details/148160086?spm=1011.2124.3001.6209

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll n,k,m; 
vector<int> a,b;
ll dp[11][60];
ll dfs(int pos,int c,bool ismax,int id,vector<int> a,bool lead)///带考虑前导零的最全数位dp板子 
{
	if(pos==-1)///边界，return需要的答案，板子要改和灵活运用的地方 
	{
		return c;
	}
	int maxn;///选择上界 
	if(ismax) maxn=a[pos];
	else maxn=9;
	if(lead&&!ismax&&dp[pos][c]!=-1)///记忆化，lead=1即没有前导零 
	{
	return dp[pos][c];	
	} 
	ll res=0;
	for(int i=0;i<=maxn;i++)
	{
		if(i==id) res+=dfs(pos-1,c+(1&&(i||lead)),ismax&&i==maxn,id,a,lead||i);
		///考虑前导零就在lead这里写i||lead 
		else res+=dfs(pos-1,c,ismax&&i==maxn,id,a,lead||i);
	}
	if(!ismax&&lead) return dp[pos][c]=res;///记忆化 
	return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    n--; 
    while(n)
    {
    	a.push_back(n%10);
    	n/=10;
	}
	while(m)
    {
    	b.push_back(m%10);
    	m/=10;
	}
	int p1=a.size()-1,p2=b.size()-1;
	for(int i=0;i<=9;i++)
	{
	memset(dp,-1,sizeof(dp));
	ll a2=dfs(p2,0,true,i,b,0);
	memset(dp,-1,sizeof(dp));
	ll a1=dfs(p1,0,true,i,a,0);
	cout<<a2-a1<<" ";	
	}
	
    return 0;
}