【100题】第三十 求从1到n这n个整数的十进制表示中1出现的次数

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

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

二，分析：这是一道广为流传的google面试题。

我们每次判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。

三，源码

#include <iostream>
using namespace std;

int NumberOf1(unsigned int n) //返回每一个数字中 1的个数 
{
      int number = 0;
      while(n)
      {
            if(n % 10 == 1)
                  number ++;

            n = n / 10;
      }

      return number;
}
int total_number(unsigned int n)
{
      int number = 0;
      for(unsigned int i = 1; i <= n; ++ i)
            number += NumberOf1(i);

      return number;
}
int main()
{
	int count=0;
	int n=12;
	cout<<"there have "<<total_number(n)<<" ' 1 ' "<<endl;
    
	return 0;
}

这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数，因此时间复杂度是O(n)。
当输入的n非常大的时候，需要大量的计算，运算效率很低。

下面是一个我看不懂的思路

char num[16];

int len, dp[16][16][2];

int dfs(int pos, int ct, int less)
{
if (pos == len)

return ct;
int &ret = dp[pos][ct][less];
if (ret != -1)

return ret;

ret = 0;
for (int d = 0; d <= (less ? 9 : num[pos] - '0'); d++)
ret += dfs(pos + 1, ct + (d == 1), less || d < num[pos] - '0');

return ret;
}

int NumOf1(int n)
{
sprintf(num, "%d", n);
len = strlen(num);
memset(dp, 0xff, sizeof(dp));
return dfs(0, 0, 0);
}