剑指offer 整数中1出现的次数

题目描述
求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

方法
显而易见应该是数位，状态为,表示第位是否为1（），以及一共有个1的1的个数。
看到很多循环写的，一旦n超过1e8就会很慢很慢了。

class Solution {
public:
    long long dp[35][2][35];
    int a[35];
    long long dfs(int pos,int st,int sum,int limit){
        if(pos==-1)
            return sum;
        if(!limit&&dp[pos][st][sum]!=-1)
            return dp[pos][st][sum];
        int up = limit ? a[pos] : 9,num=0;
        for(int i=0;i<=up;i++)
            num+=dfs(pos-1,i==1?1:0,sum+(i==1?1:0),i==up&&limit);
        if(!limit)
            dp[pos][st][sum]=num;
        return num;
    }
    int NumberOf1Between1AndN_Solution(int n)
    {
        memset(dp,-1,sizeof(dp));
        int len =0;
        while(n){
            a[len++]=n%10;
            n/=10;
        }
        return dfs(len-1,0,0,1);
    }
};