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

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

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

数据范围与提示：

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

【解析】

数位动态规划，详见代码：

#include<bits/stdc++.h>
using namespace std;
int dp[12][12];//dp[i][j]表示第i位为j时有多少个不降数
int a, b;
vector <int> digit;
//从第pos位为statu开始搜索，done表示是否有限制0，无限制，1，有限制
int dfs(int pos, int statu, int done) {
    if (pos == -1) return 1; //搜索到第-1位，即搜索完毕
    //无限制，并且已经搜索完成了，直接返回结果
    if (!done && (dp[pos][statu] != -1)) return dp[pos][statu];
    int ret = 0; //初始化计算结果
    int e;//下一位结束数字
    if (done == 0) { //无限制，到9
        e = 9;
    } else { //有限制，到这一位数字
        e = digit[pos];
    }
    //枚举当前位开始数字到结束数字
    for(int i = statu; i <= e; i++) {
        //递归计算下一位，如果当前有限制，且是最大数，则下一位也有限制
        ret += dfs(pos - 1, i, done && i == e);
    }
    //如果无限制，记录无限制的数值
    if (!done) dp[pos][statu] = ret;
    return ret;
}
//计算小于等于x的不降数数量
long long solve(int x) {
    memset(dp, -1, sizeof(dp)); //初始化dp数组
    digit.clear();//数字清空
    while(x > 0) { //拆位
        digit.push_back(x % 10);
        x /= 10;
    }
    //递归计算
    return dfs(digit.size() - 1, 0, 1);
}
int main() {
    while(cin >> a >> b) {
        cout << solve(b) - solve(a - 1) << endl;
    }
    return 0;
}