给定一个十进制正整数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的个数
Sample Input
12
Sample Output
5
分析： 数位DP 模板，可以求区间 [a,b] 中 0-9 每个的个数。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int get(int x){ // 这里处理到底要哪几个数if(x==1) return 1; //这里只要1else return 0;
}
LL dp[20][20][20]; //dp[pos][num][sum]前pos位，num已经出现了sum次
LL digit[20];LL dfs(int pos, int num, int sum, bool lead, bool limit){if(pos==0) return sum;if(!limit&&!lead&&dp[pos][num][sum]!=-1) return dp[pos][num][sum];int up=limit?digit[pos]:9;LL ans=0;if(!lead||pos==1) ans+=dfs(pos-1, num, sum+(num==0), 0, limit&&digit[pos]==0);else ans+=dfs(pos-1, num, sum, 1, limit&&digit[pos]==0);for(int i=1; i<=up; i++){ans+=dfs(pos-1, num, sum+(num==i), 0, limit&&digit[pos]==i);}if(!limit&&!lead) dp[pos][num][sum]=ans;return ans;
}LL f(LL x, int num){if(x<0) return 0;if(x==0) return num==0?1:0;int pos=0;while(x){digit[++pos]=x%10;x/=10;}return dfs(pos,num,0,1,1);
}
int main(){memset(dp, -1, sizeof(dp));LL a, b;a=1; scanf("%lld",&b); // [1,b]LL ans = 0;for(int i=0;i<=9;i++) ans+=(f(b,i)-f(a-1,i))*get(i);printf("%lld\n", ans);
}