给定一个数n，判断1-->n有多少个数字含“49”
可以用dp的方式来解决，
dp[i][0] 表示长度为i，不含"49"的数字的个数
dp[i][1] 表示长度为i，第i位为数字9的个数
dp[i][2] 表示长度为i，含”49“的数字的个数
所以，dp[i][0] 的包含dp[i][1]的
状态转移方程如下：
dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1]; 长度为i不含"49"，可以由长度为i-1不含"49"的数字在第i位补上0->9得到，并减去以9开头，补上4，得到含"49"的数字的个数
dp[i][1] = dp[i-1][0]; 在长度i-1不含"49"的数字的第i为补上9
dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; 长度为i含"49"，可以由长度为i-1含"49"的数字在第i位补上0->9得到，并加上以9开头，补上4，得到含"49"的数字的个数
刚开始的时候我注意到一个问题，就是在第i位补0的情况。
就是dp[2][2] = 1(数字49)
dp[3][2] = dp[2][2] * 10 + dp[2][1], 那么dp[3][2]不是把数字049给算在内了吗。
事实上，确实是这样子，而且也是有问题的，看了统计部分的代码才知道怎么回事。
dp完后就要统计小于等于n的数中有多少个数字含“49”
统计区间[1,n],从高到低枚举哪一位比n+1小，比如说n+1=5001;
千位比n小，那么可以取值0-->4 ans += 5 * dp[3][2]; 要知道dp[3][2] 统计了数字"49","149","249","349","449","490","491","492","493","494","495","496","497","498","499", “549","649","749","849","949"
所以当千位取0时，就将这些2位数和3位数给统计进去了。 这就是为什么dp[3][2]要统计数字“049”的原因
百位比n小，没有东西比0小， ans += 0 * dp[2][2];
十位比n小，没有东西比0小， ans += 0 * dp[1][2];
个位比n小，那么可以取值1， ans += 1 * dp[0][2];
当然还有一些特殊情况没有讨论，详细见源代码
1 #include2 #include 3 typedef __int64 LL; 4 LL dp[22][3]; 5 /* 6 dp[i][0] 长度为i，不含49的个数 dp[i][0] 包含dp[i][1] 7 dp[i][1] 长度为i，含前缀9的个数 8 dp[i][2] 长度为i，含49的个数 9 */10 void init()11 {12 int i;13 dp[0][0] = 1;14 for(i=1; i<=20; ++i)15 {16 dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];//长度为i，不含49的个数，可以由长度为i-1，不含49的数字在第i为添加0-9，17 dp[i][1] = dp[i-1][0];//在长度为i-1，不含49的数字前面添个918 dp[i][2] = dp[i-1][2]*10 + dp[i-1][1];//长度为i，含49的个数，可以在含49的数字前面添加0-9，在9开头的数字前面添加419 }20 }21 int num[22];22 int main()23 {24 init();25 printf("%d\n",dp[3][2]);26 int t,i;27 scanf("%d",&t);28 while(t--)29 {30 LL n;31 int len = 0;32 scanf("%I64d",&n);33 n+=1;34 while(n)35 {36 num[++len] = n % 10;37 n /= 10;38 }39 num[len+1] = 0;40 LL ans = 0;41 bool flag = false;42 for(i=len; i>=1; --i)43 {44 45 ans += num[i] * dp[i-1][2];46 if(flag)//数字n的前面含有49，47 ans += num[i] * dp[i-1][0];//后面的i-1位数字有多少个不含49，那么也可以算含有"49"的数字48 if(!flag && num[i]>4)//如果第i位的数字大于4，那么第i为取值4的时候49 ans += dp[i-1][1];//后面的i-1位数字有多少个是以9开头，那么也可以算含有"49"的数字50 if(num[i+1]==4 && num[i]==9)51 flag = true;52 }53 printf("%I64d\n",ans);54 55 }56 return 0;57 }
数位dp参考资料：http://wenku.baidu.com/link?url=zSYj4Dfy46C-l4L-ryGsuhzUE_SY5M6XfniTpfTYbHnHhrvvrmvN7DwG-OonqHvANFbl5SWE_46COUWxTNhuXJ8WRr6YugeJKFdDKIJSK4e