【题目来源】
【题目描述】
科协里最近很流行数字游戏。
某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123
，446。
现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。
注意：不降数不能包含前导零。
【输入格式】
输入包含多组测试数据。
每组数据占一行，包含两个整数 a 和 b。
【输出格式】
每行给出一组测试数据的答案，即 [a,b] 之间有多少不降数。
【输入样例】
1 9
1 19
【输出样例】
9
18
【数据范围】
1≤a≤b≤2^31−1
【算法分析】
● 数位DP（Digit Dynamic Programming）是一种用于解决数字数位相关计数问题的动态规划算法。其核心思想是将数字按位拆解，通过递归或递推的方式处理每一位的选择，并利用记忆化搜索来避免重复计算，从而高效统计满足特定条件的数字数量。
● 数位DP通过记录前导零、数位限制等状态，将问题复杂度从 O(n) 降低到 O(log n)，能够处理非常大的数字范围（如 10^18）。其实现通常是将统计 [le, ri] 的问题转化为统计 [1, ri] 和 [1, le-1] 的结果相减。
● 数位DP题型的特点：求某个区间 [le, ri] 内，满足某种性质的数的个数。
● 数位DP在本题中的应用技巧：从高位到低位填数，要分类讨论。
（一）f[i][j] 表示 i 位数且最高位为 j 的不降数的个数。
（二）利用短除法将数字 n 对 10 求余所得的各位依次放入一个名为 v 的 vector 中。然后，从右至左枚举 v。假设枚举到第 i 位，第 i 位上的数字是 x，讨论如下（其中，pre 记录第 i 位之右存放的数）。
将 x 划分为 0~x-1 和 x 两类，如果第 i 位填 0~x-1，则左边每一位都可以填 0~9；如果第 i 位填 x，则固定第 i 位，然后再按上述方法讨论第 i 位的左边一位。
● 不降数的个数应该与位数以及最高位数字有关。设 f[i][j] 表示 i 位数且最高位为 j 的不降数的个数。
【算法代码】
#include<bits/stdc++.h>
using namespace std;const int N=15; //数的位数
int f[N][N]; //f[i][j]表示i位数且最高位为j的不降数的个数/*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];
}*/void init() {for(int i=0; i<=9; i++) f[1][i]=1;for(int i=2; i<N; i++) {int sum=0;for(int j=9; j>=0; j--) {sum+=f[i-1][j];f[i][j]=sum;}}
}int dp(int n) {if(n==0) return 1;vector<int> v;while(n) {v.push_back(n%10);n/=10;}int cnt=0,pre=0;for(int i=v.size()-1; i>=0; i--) {int x=v[i];for(int j=pre; j<x; j++) {cnt+=f[i+1][j];}if(pre>x) break;pre=x;if(i==0) cnt++;}return cnt;
}int main() {init();int le,ri;while(cin>>le>>ri) {cout<<dp(ri)-dp(le-1)<<endl;}return 0;
}/*
in:
1 9
1 19out:
9
18
*/
【参考文献】
https://www.bilibili.com/video/BV1Ff4y1e7YW/