题目描述:

给定一个十进制正整数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的个数

题目思路:
数位dp,假设现在已经枚举到百位之前枚举的数字是131,那么接下来的需要计算的所有数字都是131xx,
(也就是从是13100~13199)100个数字,那么也就是说前面路径131中的两个1一共出现了100次,所以要乘起来;
后一部分dp[pos]很好理解,就是计算在13100到13199之间的数131xx在xx部分会出现的1的数目;
05-11 20:57