比如说搜741，慢慢往下推进
第一次算的是100-600多的windy数
然后判断4和7是否差的大于等于2，若大于等于，则把last更新成4
此时已经有f[3][6]到f[3][1]，三位数，最高位为6的所有windy数
然后再找f[2][3]到f[2][0]，继续判断4和1，更新last

相反，若输入761
则相当于算f[3][6]到f[3][1] + f[2][0]到f[2][4],然后会直接break

就是，当倒数第二位小于等于第一位时，可以分情况枚举
但枚举时只能枚举到该位-1的数，如761，当枚举到第二位时只能到5，因为可以保证50-59都小于概数，
当枚举完5时，就要切换到下一位了

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int N=15;

int f[N][N];

//要分两种情况，答案等于size位的，和答案小于size位的
int dp(int n)
{
    int res=0;
    int last=-2;
    if(n==0) return 0;
    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n=n/10;
    }
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(i==nums.size()-1)
        {
            for(int j=1;j<x;j++)
            {
                if(abs(j-last)>=2)
                {
                    res+=f[i+1][j];
                }
            }
        }
        else
        {
            for(int j=0;j<x;j++)
            {
                if(abs(j-last)>=2)
                {
                    res+=f[i+1][j];
                }
            }
        }
        if(abs(x-last)>=2) last=x;
        else break;

        if(i==0) res++;
    }
    for(int i=1;i<nums.size();i++)
    {
        //这里j表示的是最高位，所以不能是0
        for(int j=1;j<=9;j++)
        res+=f[i][j];
    }

    return res;
}

int main()
{
    int l,r;
    cin>>l>>r;

    for(int i=0;i<=9;i++)
    f[1][i]=1;

    for(int i=2;i<=N;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(abs(j-k)>=2)
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }


    }

    cout<<dp(r)-dp(l-1);

    return 0;
}

二刷

注意初始化时，j要从0开始循环，因为除了最高位以外，别的位都可以为0
最高位特判时在dp中判断
要注意最后加上<num.size()位的情况，循环里枚举的都是num.size()位的情况(最高位枚举[1,x)),后面的都有last限制，因此循环中计算的是num.size()位的情况

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
const int N=11;

int f[N][N];

int dp(int n)
{
    if(n==0) return 0;

    int res=0;
    int last=-2;
    vector<int> num;

    while(n)
    {
        num.push_back(n%10);
        n=n/10;
    }
    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];
        if(i==num.size()-1)
        {
            for(int j=1;j<x;j++)
            {
                //一共i+1位，最高位是j
                res+=f[i+1][j];
            }
        }
        else
        {
            for(int j=0;j<x;j++)
            {
                if(abs(j-last)>=2)
                {
                    res+=f[i+1][j];
                }
            }
        }
        if(abs(x-last)>=2) last=x;
        else break;

        if(i==0) res++;
    }
    //特殊枚举答案小于a.size()位的数
    for(int i=1;i<num.size();i++)
    {
        //这里j表示的是最高位，所以不能是0
        for(int j=1;j<=9;j++)
        res+=f[i][j];
    }
    return res;
}

int main()
{
    for(int i=0;i<=9;i++) f[1][i]=1;
    for(int i=2;i<=N-1;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(abs(j-k)>=2)
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }
    }
    int l,r;
    cin>>l>>r;
    cout<<dp(r)-dp(l-1);
    return 0;
}

三刷，第一遍还是没能过掉啊，又发现了几个坑

1. 在计算f[i][j]时，要注意第二层循环j要从0开始，不能从1开始，要从0开始，可不能被“首位不能为0”迷惑，原因如下
   因为除了dp时的首位不能为0外，在计算f[i][j]时，如计算f[3][7]，以7开头的三位数，那首位7确定了，在计算后面两位的方案数时，需要用到f[2][0],即以0开头的两位数，703,702,704等也满足。

2. 在做dp时是可以剪枝的，遇到abs(x-last)<2的情况可以直接break

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
const int N=15;

long long f[N][N];

int dp(int n)
{
    vector<int> num;
    while(n)
    {
        num.push_back(n%10);
        n=n/10;
    }
    int res=0;
    int last=-1;

    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];
        //首位不能为0，特殊处理
        if(i==num.size()-1)
        {
            for(int j=1;j<x;j++)
            {
                res+=f[i+1][j];
            }
        }
        else
        {
            for(int j=0;j<x;j++)
            {
                if(abs(j-last)>=2)
                {
                    res+=f[i+1][j];
                }
            }
        }

        if(abs(x-last)>=2) last=x;
        else break;
        if(i==0) res++;
    }


    if(num.size()>1)
    {
        for(int i=1;i<=num.size()-1;i++)
        {
            for(int j=1;j<=9;j++)
            {
                res+=f[i][j];
            }
        }
    }

    return res;
}

int main()
{
    for(int i=0;i<=9;i++)
    {
        f[1][i]=1;
    }
    for(int i=2;i<=N-1;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(abs(k-j)>=2)
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }
    }

    int l,r;
    cin>>l>>r;
    cout<<dp(r)-dp(l-1);
    return 0;
}