学步园

不含前导零且相邻两个数字之差至少为2的正
整数被称为windy数,求windy数的个数

非递归

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int l, r;
int dp[33][11];
int abs(int a, int b) {
    a -= b;
    return a > 0 ? a : -a;
}
void init() {
	int i, j, k;
	for(i = 0; i <= 9; i++)  dp[1][i] = 1;
	for(i = 2; i < 33; i++)
		for(j = 0; j <= 9; j++)
			for(k = 0; k <= 9; k++) if(abs(k-j) >= 2)
				dp[i][j] += dp[i-1][k];
}
int gao(int n) {
    if(n < 10) return n;
	int a[33], len = 0;
	while(n) {a[len++] = n % 10; n /= 10;}
	a[len] = 10000; // pay attentoin
	bool flag = 0;
	int i, j;
	int ans = 1; // zero
	for(i = len-1; i >= 1; i--)
		for(j = 1; j <= 9; j++)
			ans += dp[i][j];
	for(i = len-1; i >= 0; i--) {
		for(j = (i==len-1) ? 1 : 0; j < a[i]; j++) {
			if(flag || abs(a[i+1]-j) < 2 )  continue;
			ans += dp[i+1][j];
		}
		if( abs(a[i+1]-a[i]) < 2) flag = 1;
	}
	return ans;
}
int main() {
    ios :: sync_with_stdio(0);
	init();
	while(cin >> l >> r) {
		cout << gao(r+1) - gao(l) << endl;
	}
	return 0;
}

递归

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
int l, r;
int a[11];
int dp[11][10];
int dfs(int len, int dig, bool lim) {
	if(!len) return 1;
	if(!lim) {
		if( ~dp[len][dig]) return  dp[len][dig];
	}
	int i, m = lim ? a[len-1] : 9;
	int ret = 0;
	for(i = 0 ; i <= m; i++) if(abs(i-dig) >= 2)
		ret += dfs(len-1, i, lim && i == m);
	dp[len][dig] = ret;
	return ret;
}
int gao(int n) {
	int len = 0;	
	while(n) {a[len++] = n%10; n/=10; }
	int i, j;
	memset(dp, -1, sizeof(dp));
	int ret = 1; // zero
	for(i = len-2; i >= 0; i--)
		for(j = 1; j <= 9; j++)
			ret += dfs(i, j, 0);
	for(i = 1; i <= a[len-1]; i++) 
		ret += dfs(len-1, i, i == a[len-1]);
	return ret;
}
int main() {
	ios :: sync_with_stdio(0);

	while( cin >> l >> r)
		cout << gao(r) - gao(l-1) << endl;
	return 0;
}