51nod 1042 数字0-9的数量【数位dp】

题目：http://www.51nod.com/onlineJudge/questionCode.html#!PRoblemId=1042

题意：

分析：

做了一会儿没刚出来，囧 // 这题和1009差不多 1009看这篇博客写得很清楚，会了这题再来写这题就容易了。 http://blog.csdn.net/wyg1997/article/details/52169036

假设现在求21905内数字1的个数： 个位：它出现1的数为：1 ~ 21901，一共 2190 - 0 + 1 = 2191 十位：它出现1的数为：1x ~ 2181x （x 从0到9）一共：（218 - 0 + 1）*10 = 2190 百位：它出现1的数为：1xx ~ 211xx ，一共：（21 - 0 + 1）* 100 = 2200 千位：它出现1的数为：1xxx ~ 11xxx 和 21000 ~ 21905 ，那么很明显，这个情况就比较特殊了，为什么呢？下面再说，我们先计数，一共：（1 - 0 + 1）*1000 + （905 - 0 + 1）= 2000 + 906 = 2906 万位：它出现1的数为：1xxxx ~ 1xxxx，一共：10000

为什么计算千位的时候特殊呢？因为这个时候千位是1，那么21905中，905是确定的，而不是像之前那样任意取xxx。

代码：