$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. f[i][j] 表示一共有 i 位且最高位是 j 的不降数的个数，last 存储上一位是什么数
2. dp(n) 表示 0 ～ n 中不降数的个数
3. 首先预处理，公式 f[i][j] += f[i-1][k] (j <= k <= 9)
4. 对于 abcdefg，当前位可以填 last ～ a - 1，res += f[i + 1][j]
5. 如果当前位比前一位要小就直接 break
6. 考虑最后一位，如果没有退出循环说明本身就是一个不降数，res ++

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 15;

int f[N][N];

//预处理
void init()
{
    for(int i=0;i<=9;i++) f[1][i]=1;
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            for(int k=j;k<=9;k++)
                f[i][j]+=f[i-1][k];
}

// 0 ～ n 中不降数的个数
int dp(int n)
{
    if(!n) return 1;

    vector<int> nums;
    while(n) 
    {
        nums.push_back(n%10);
        n/=10;
    }

    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];

        if(x<last) break; //当前数比前一个数要小

        for(int j=last;j<x;j++) res+=f[i+1][j]; //当前位填 last ～ x - 1

        last=x;

        if(!i) res++; //这个数本身就是一个不降数
    }

    return res;
}

int main()
{
    init();

    int l,r;

    while(cin>>l>>r) cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}