输入一个整数 n ，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12 ，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，1 ，10，11 和 12 ，其中 “1” 一共出现了 5 次。

样例

1
2

输入： 12
输出： 5

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        vector<int> v;
        while(n) v.push_back(n%10),n/=10;
        
        memset(dp,-1,sizeof dp);
        return dfs(v,v.size()-1,0,1);
    }
    #define ll long long
    //dp[pos][cnt] 表示枚举到 pos 位置， 有cnt 个1 的排列的数量
    int dp[32][32];
    ll dfs(vector<int> &v, int pos,int cnt1,int limit) {
        if(pos < 0) return cnt1;
        if(!limit && dp[pos][cnt1]!=-1) return dp[pos][cnt1];
        ll res= 0;
        ll maxNum = limit? v[pos]:9;
        for(int i=0;i<=maxNum;++i) {
            if(i==1) res += dfs(v,pos-1,cnt1+1,limit&&(i==maxNum));
            else
                res+= dfs(v,pos-1,cnt1,limit && (i==maxNum));
        }
        if(!limit)
            dp[pos][cnt1] = res;
        return res;
        
    }
};