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;
}
)
)
