Windy数

限制条件：不含前导0且相邻两个数字之差至少为2

1.把求[l,r]转换成求[1,l-1]&[1,r]，然后利用类似前缀和的思想

2.把长度短的数字补全前导0

通过以上两步，就把两种限制条件都变成了数位的维度

从高位到低位去枚举---->dfs

dfs都需要记录哪些状态？

1.枚举到了哪一位

2.前一位数字是多少（要保证数位之差>=2）

3.这一位可以填哪些数字

前两个很好维护，我们看第三个参数，以12345为例

由此，对于位置x，可以得出结论：

x填的数有两种可能性

?dfs需要参数：pos(当前位数)pre(前一位数字是多少)flag(是否前面每一位都和上限数字相同)

dfs(pos,pre,flag){
    if(pos<0)return 1;  //已经枚举完每一位
    if(flag)up=limit[pos]    //前面都是贴着放的，这一位可以填的最大数字是上限数字
    else up=9;
    result =0;
    for(int i=0;i<=up,i++){
        if(i与pre相差>=2)
            result+=dfs(pos-1,i,flag && (i==limit[pos])) //flag代表前一位是不是贴着放的，i==limit[pos]代表这一位
    }
    return result;
}

接下来考虑优化该dfs——数位dp

我们会发现，如果flag==false，整个dfs后面的过程与limit将毫无关系，我们可以把这个状态的答案记录下来——这就是数位dp的思想所在

dfs(pos,pre,flag){
    if(pos<0)return 1;  //已经枚举完每一位
    if(!flag && dp[pos][pre]!=-1)return dp[pos][pre];    //记录过这个状态
    if(flag)up==limit[pos] else up=9;
    result =0;
    for(int i=0;i<=up,i++){
        if(i与pre相差>=2)
            result+=dfs(pos-1,i,flag && (i==limit[pos])) //flag代表前一位是不是贴着放的，i==limit[pos]代表这一位
    }
    if(!flag) dp[pos][pre]=result;
    return result;
}

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll; 
//用dp[pos][pre]代表枚举到第pos位，上一位数是pre的方案总数 
ll dp[15][15];
int limit[15];	//记录每个数位上的最高位 
ll L,R;

//pos当前位置,pre前一位数,st判断前面是否全是0,flag最高位限制 
ll dfs(int pos,int pre,int st,int flag){
	if(pos<0) return 1;	//枚举结束 
	//记忆化 
	if(!flag && !st && dp[pos][pre]!=-1) return dp[pos][pre];
	int up=flag?limit[pos]:9;
	int ans=0;
	for(int i=0;i<=up;i++){
			if(abs(i-pre)<2) continue;//不符合题意，继续 
		if(st&&i==0) ans+=dfs(pos-1,-2,1,flag&&i==up);//如果有前导0，下一位随意 
		else ans+=dfs(pos-1,i,0,flag&&i==up);//如果没有前导0，继续按部就班地搜 
	}
	if(!flag && !st) dp[pos][pre]=ans;	//没有最高位限制和前导0时记录结果
	return ans; 
}

int solve(ll x){
	int pos=0;
	//分解数位 
	while(x){
		limit[pos++]=x%10;
		x/=10;
	}
	memset(dp,-1,sizeof(dp));
	return dfs(pos-1,-2,1,1); 
}

int main(){
	cin>>L>>R;
	cout<<solve(R)-solve(L-1);
}