1009 数字1的数量
基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注
给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。
例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。
Input
输入N(1 <= N <= 10^9)
Output
输出包含1的个数
Input示例
12
Output示例
5
这道题用找规律，统计每一位上1出现的次数，很简单就能写出来。
https://blog.csdn.net/wyg1997/article/details/52169036 ( 找规律）
http://www.knowsky.com/1046368.html （数位dp）
这两个博客写的很详细。
既然这道题是数位dp，那么我想了好久怎么用数位dp写这道题，写了三个多小时才写出来，中间还差点放弃。
这道题作为数位dp入门题就过分了吧（可能是我太菜了吧），我数位dp都写了8道题了，这个题依旧想了3个小时，才写出来。（建议数位dp的新手还是先去做 （不要62） 吧）
int dp[pos], //dp[i]表示后i位从0遍历到99999(共i+1个9)，能出现多少个1
代码稍微解释了一下，应该能看懂吧
#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long LL;
const LL mod=1e9+7;
const int M=13;
using namespace std;
const int N =1e5+100;
int a[10],dp[10];//dp[i]表示后i位从0遍历到99999(i+1个9)，能出现多少个1
int v[10]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};//存10的平方，立方， 等等
int dfs(int pos,int num,int limit)//num表示从最高位到（pos+1）位出现了多少个1
{
if(pos==-1) return num;
if(!limit&&dp[pos]!=-1) return num*v[pos]+dp[pos];
//如果后dp[pos]已经存的有值了，那么num*(10^(pos+1))直接加上dp[pos];
int up=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=up;i++)
ans+=dfs(pos-1,num+(i==1),limit&&i==up);
return limit?ans:dp[pos]=ans;
}//其余都是板子
int slove(int x)
{
int pos=0;//习惯不同，代码就不一样，pos从0开始的
for(;x;x/=10)
a[pos++]=x%10;
return dfs(pos-1,0,1);
}
int main()
{
mem(dp,-1);
int n;
scanf("%d",&n);
printf("%d\n",slove(n));
}