1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 int dp[15][15],num[15];//len last 7 int a,b; 8 9 int dfs(int len,int last,bool shangxian,bool qdling) 10 { 11 if(len==0) return 1; 12 if(!qdling&&!shangxian&&dp[len][last]!=-1) 13 return dp[len][last]; 14 int p,cnt=0,maxx=(shangxian?num[len]:9); 15 for(int i=0;i<=maxx;i++) 16 { 17 if(abs(i-last)<2)continue; 18 p=i; 19 if(qdling&&i==0) p=-233; 20 cnt+=dfs(len-1,p,(shangxian)&&(i==maxx),(p==-233)); 21 } 22 if(!shangxian&&!qdling) dp[len][last]=cnt; 23 return cnt; 24 } 25 26 int solve(int x) 27 { 28 int k=0; 29 while(x) 30 { 31 num[++k]=x%10; 32 x/=10; 33 } 34 memset(dp,-1,sizeof(dp)); 35 return dfs(k,-233,true,true); 36 } 37 38 int main() 39 { 40 scanf("%d%d",&a,&b); 41 printf("%d ",solve(b)-solve(a-1)); 42 }