题目大意：在区间[a, b]中有多少个数字是逐位不递减的？

题目描述

科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

输入

有多组测试数据。每组只含两个数字 a,b，意义如题目描述。

输出

每行给出一个测试数据的答案，即 [a,b] 之间有多少不降数。

样例输入

1 9
1 19

样例输出

9
18

对于全部数据，$1≤a≤b≤2^{31}−1$。

解题思路

本题数据范围比较小，可以直接暴力通过。

程序实现

需要求区间[x, y]每一位不递减的数字的数量，可以暴力填这些数字的每一位，每得到一个数字，如果满足区间范围则加1。

递归结束条件：超过y。时间复杂度约$O(10!)$

写成数位DP的形式，可以进行剪枝。

首先区间[x, y]中符合要求的数字个数，可以转成前缀和：前y个符合要求的数量减去前x-1个符合要求的数量。

对于前n个符合要求的数量，我们可以把n逐位取出，然后填数字的时候，就可以根据该位的值进行剪枝。

从高位开始，如果之前的位都是相等（没有超过n），那么下一位不能比对应位大，否则可以填到9。

注意，最高位可以填零，即相当于位数少的数字。

加入记忆化，就是数位DP了！f[k][x][p]表示从高位开始填，第k位填x时比原数小(p为真则小，否则高位全部相等)的后面填法的方案数。

后面的填法，取决于是否比原数大，从几开始填，以及剩下多少位，这些都确定了，那么后面的如果搜索过就可以记下来，下次直接返回。