记忆化搜30pts求调

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int num[20];   //存放x的数位(从高到低)
int dp[20][20][2];
int length;
int dfs(int len,int pre,bool limit)   //需要考虑的最后len个数，pre是上一位的数字,limit表示取数有无限制
{
    if(len==0) return 1;
    if(dp[len][pre][limit]!=-1) return dp[len][pre][limit];
    int ans=0;
    int pos=length-len;
    if(!limit) //不受限
    {
        if(pre==10)
        {
            ans+=dfs(len-1,10,0);
            for(int i=1;i<=9;i++)  //随便选
                ans+=dfs(len-1,i,0);
        }
        else
            for(int i=0;i<=9;i++)
                if(abs(i-pre)>=2) ans+=dfs(len-1,i,0);
    }
    else//受限
    {
        if(pre==10)//之前从未选择数字
        {
            ans+=dfs(len-1,10,0);   //继续不选数字,但不再受限
            for(int i=1;i<=num[pos];i++)  //选肯定不能选0
                if(i==num[pos]) ans+=dfs(len-1,i,1);  //选了最大值仍受限
                else ans+=dfs(len-1,i,0);
        }
        else
        {
            for(int i=0;i<=num[pos];i++)//选了要考虑0了
                if(abs(i-pre)>=2)   //也要考虑相邻差值
                    if(i==num[pos]) ans+=dfs(len-1,i,1);  //选了最大值仍受限
                    else ans+=dfs(len-1,i,0);
        }
    }
    return dp[len][pre][limit]=ans;
}
int compute(int x)  //0~x的windy数个数
{
    int t=0,temp=1,len=1;
    while(temp*10<=x) temp*=10,len++;
    length=len;
    while(x)
    {
        num[t]=x/temp;
        x%=temp;
        temp/=10;
        t++;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(len,10,1);
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<compute(b)-compute(a-1);
}