题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

数位dp： 时间复杂度为 n位数*10 接近常熟 分成n位数字讨论即可

public:
    vector<int> v;
    int NumberOf1Between1AndN_Solution(int n) {
        
        while(n){
            v.push_back(n%10);
            n/=10;
        }
        reverse(v.begin(),v.end());
        int len=v.size();
        int ans=0;
        for(int i=0;i<len;i++){
            if(i==0){
                if(v[i]>1) ans+=pow(10,len-1-i);
                else ans+=fend(i+1)+1;
//                 cout<<ans<<endl;
            }else{
                int qz=fsta(i),hz=fend(i+1);
                int p10=pow(10,len-i-1);
                if(v[i]==0) ans+=p10*qz;
                else if(v[i]>1) ans+=(qz+1)*p10;
                else ans+=qz*p10+hz+1;
            }
        }
        return ans;
    }
    
    int fsta(int j){
        int temp=0;
        for(int i=0;i<j;i++){
            temp=temp*10+v[i];
        }
        return temp;
    }
    
    int fend(int j){
        int temp=0;
        for(int i=j;i<v.size();i++){
            temp=temp*10+v[i];
        }
        return temp;
    }
};