C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-10-19 17:16:39

#include <iostream>
#include <cstring>
using namespace std;
int dp[32][10], digit[32], len;
int dfs(int pos, int pre, bool up) {
	if(!pos)	return 1;
	if(!up&&dp[pos][pre]!=-1)	return dp[pos][pre];
	int ret=0,upmax=up?digit[pos]:9;
	for(int i=0; i<=upmax; i++) {
		if(i<pre)continue;
		ret+=dfs(pos-1,i,up&&i==upmax);
	}
	if(!up)return dp[pos][pre]=ret;
	return ret;
}
int solve(int x) {
	len = 0;
	memset(dp, -1, sizeof(dp));
	while (x) {
		digit[++len] = x % 10;
		x /= 10;
	}
	return dfs(len, 0, true);
}
int main() {
	int a, b;
	while (cin >> a >> b) {
		cout << solve(b) - solve(a-1) << endl;
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 328K, 提交时间: 2023-02-18 14:49:46

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a,b,ans;

void dfs(ll u,ll c)
{
	if(u>b) return;
	else if(u>=a) ans++;
	for(int i=c;i<10;i++)  dfs(u*10+i,i);
}

int main()
{
	while(cin >> a >> b){
		ans=0;
        dfs(0,1);
		cout << ans << endl;
	}
	return 0;
}