不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

这是一道数位dp,设dp[i][j]，dp[i][j]表示i为长度，j为最高位上的数字的个数。

#include<stdio.h>

#include<string.h>

#include<math.h>

int dp[100][14];

void init()

{

int i,j,k;

memset(dp,0,sizeof(dp));

for(j=0;j<=9;j++)dp[1][j]=1;

for(i=2;i<=11;i++){

for(j=0;j<=9;j++){        //这里要注意不能从j=1开始循环，因为10010这样是符合条件的，但0010的最高位0是0 

for(k=0;k<=9;k++){

if(fabs(j-k)>1){

dp[i][j]+=dp[i-1][k];

}

}

}

}

}

int cal(int x)  //计算的是（0,a)区间的windy数 

{

int m=0,i,j,a[100],ans=0;

memset(a,0,sizeof(a));

while(x>0){

a[++m]=x%10;

x=x/10;

}

for(i=1;i<=m-1;i++){       //先算数字长度小于m的windy数 

for(j=1;j<=9;j++){     //因为不含前导0，所以从j=1开始算 

ans=ans+dp[i][j];

}

}

for(j=1;j<a[m];j++){     //再算数字长度等于m但最高位小于a[m]的windy数 

ans=ans+dp[m][j];

}

for(i=m-1;i>=1;i--){   //最后一次将最高位变成和原来的数一样，就是接近原来的数 

for(j=a[i]-1;j>=0;j--){    

if(fabs(a[i+1]-j)>1){

ans=ans+dp[i][j];

}

}

if(fabs(a[i]-a[i+1])<=1)break;  //如果这个时候前面的数字不符合windy数的要求，后面的数也一定不符合 

}

return ans;

}

int main()

{

int n,m,i,j;

init();

while(scanf("%d%d",&n,&m)!=EOF)

{

printf("%d\n",cal(m+1)-cal(n));

}

return 0;

}