AcWing 1082 数字游戏 题解（动态规划—DP—数位DP）
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int a, b, n;
int f[N][N];//表示一共有i位，最高位为j的数的个数
void init()
{
for(int i = 0; i <= 9; i ++ ) f[1][i] = 1;//将所有一位数字的方案数记录为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];//i-1表示第i位后面的一位，从高位向低位看，越往后需要的位数越小,k表示比j大的数
}
}
}
}
int dp(int n){//求1~n不降数的个数
if(!n) return 1;//如果是0，也是一个不下降数字，返回个数1
vector<int>num;
while(n){//把n逆序存储，这样从最高位开始遍历num时，后一位就是他的低位，符合题意
num.push_back(n % 10);
n /= 10;
}
int res = 0;//记录方案数
int last = 0;//记录上一位的数
for(int i = num.size() - 1; i >= 0; i -- ){
int x = num[i];//选出当前位的数字
for(int j = last; j < x; j ++ ){//枚举比上一位大的数字，不能大于当前位
res += f[i + 1][j];//枚举位数+1且下一位大于等于上一位的数的个数
}
if(x < last) break;//如果枚举到的数小于上一位，就不可能出现不降数，直接退出循环
last = x;//记录这一位的值
if(!i) res ++ ;//如果到达最后一位，方案数 ++
}
return res;
}
int main()
{
init();
while(cin>>a>>b) cout<<dp(b) - dp(a - 1)<<endl;
return 0;
}